/ Randle /

记录详情

Runtime Error


  
# 状态 耗时 内存占用
#1 Accepted 8ms 380.0 KiB
#2 Accepted 10ms 376.0 KiB
#3 Accepted 10ms 364.0 KiB
#4 Runtime Error 243ms 23.535 MiB
#5 Runtime Error 243ms 23.477 MiB
#6 Time Exceeded ≥1004ms ≥16.852 MiB
#7 Time Exceeded ≥1003ms ≥16.922 MiB
#8 Time Exceeded ≥1005ms ≥16.82 MiB
#9 Time Exceeded ≥1008ms ≥16.887 MiB
#10 Time Exceeded ≥1005ms ≥16.75 MiB

代码

//Williams Wu
/*#include <EGE.height>  //绘图头文件
#define SHOW_CONSOLE*/
/*#include <cstdio> //定义输入/输出函数
#include <iostream> //数据流输入/输出
#include <algorithm> //STL通用算法
#include <cmath> //定义数学函数
#include <cstdlib> //定义杂项函数及内存分配函数
#include <cstring> //字符串处理
#include <string> //字符串类
#include <ctime> //定义关于时间的函数*/
/*#include <bitset> //STL位集容器
#include <cstype> //字符处理
#include <cerrno> //定义错误码
#include <complex> //复数类
#include <clocale> //定义本地化函数
#include <deque> //STL双端队列容器
#include <exception> //异常处理类
#include <fstream> //文件输入/输出
#include <functional> //STL定义运算函数(代替运算符)
#include <limits> //定义各种数据类型最值常量
#include <listt> //STL线性列表容器
#include <mapp> //STL映射容器
#include <iomanip> //参数化输入/输出
#include <ios> //基本输入/输出支持
#include <iosfwd> //输入/输出系统使用的前置声明
#include <istream> //基本输入流
#include <ostream> //基本输出流
#include <queue> //STL队列容器
#include <sett> //STL集合容器
#include <sstream> //基于字符串的流
#include <stackk> //STL堆栈容器
#include <stdexcept> //标准异常类
#include <streambuf> //底层输入/输出支持
#include <utility> //STL通用模板类
#include <vector> //STL动态数组容器
#include <cwchar.height>//宽字符处理及输入/输出
#include <cwctype.height> //宽字符分类*/
#include <bits/stdc++.h>
using namespace std;
#define rep(x,y,tp) for(int x=(y);(x)<=(tp);(x)++)
#define rep_(x,y,tp) for(int x=(y);(x)<(tp);(x)++)
#define repf(x,y,tp) for(int x=(y);(x)>=(tp);(x)--)
#define repf_(x,y,tp) for(int x=(y);(x)>(tp);(x)--)
#define inf 0x3f3f3f3f  //0x7fffffff
#define cle(x) memset(x,0,sizeof(x))
#define clemin(x) memset(x,-1,sizeof(x))
#define clemax(x) memset(x,0x3f,sizeof(x))  //127
const double PI=3.14159265358979323846264338327950288419716939937510;
const double E=2.7182818284590452353602874713526624977572470936999596;
const double eps=0.000000001;
typedef long long LL;
inline LL max(LL x,LL y){return x>y?x:y;}
inline int min(int x,int y){return x<y?x:y;}
inline int gcd(int x,int y){return y?gcd(y,x%y):x;}
///////////////////////optimize//////////////////////////
//#pragma GCC optimize("O2") //O2优化
//#pragma GCC optimize("Ofast") //Ofast优化
//ios::sync_with_stdio(false); //取消同步(加快流输入输出速度)
//////////////////////////read///////////////////////////
template <typename T>
inline void read(T& x){char id;x=0;bool flag=false;id=getchar();
  while(id>'9'||id<'0'){if(id=='-')flag=true;id=getchar();}
  while((id<='9'&&id>='0')) {x=x*10+id-'0';id=getchar();}if(flag)x*=-1;}
template <typename T>
inline void read(T& x,T& y){read(x);read(y);}
template <typename T>
inline void read(T& x,T& y,T& z){read(x);read(y);read(z);}
/////////////////variables&functions/////////////////////

int siz[1000100],dis[1000100],vis[1000100],head[1000100];
int n,tot=0,ans=0,root=0;

struct node{
    int u,v,nextt;
}tree[1000100];

inline void add(int u,int v) 
{
    tree[++tot].u=u;
    tree[tot].v=v;
    tree[tot].nextt=head[u];
    head[u]=tot;
}

void dfs1(int x,int fa) 
{
    for(int i=head[x];i;i=tree[i].nextt) 
    {
        int v=tree[i].v;
        if(v!=fa)
        {
            dfs1(v,x);
            dis[x]+=dis[v]+siz[v];
            siz[x]+=siz[v];
        }   
    }
    siz[x]++;
}

void dfs2(int x,int fa) 
{
    if(x==1) vis[x]=dis[x];
        else vis[x]=vis[fa]+n-2*siz[x];
    for(int i=head[x];i;i=tree[i].nextt)
    {
        int v=tree[i].v;
        if(v!=fa) dfs2(v,x); 
    }
}

int main() 
{
    //freopen("tree.in","r",stdin);
    //freopen("tree.out","w",stdout);
    read(n);
    rep_(i,1,n)
    {
        int u,v;
        read(u,v);
        add(u,v);
        add(v,u);
    }
    dfs1(1,0);
    dfs2(1,0);
    rep(i,1,n)
    {
        if(ans<vis[i]) 
        {
            root=i;
            ans=vis[i];
        }
    }
    printf("%d\n",root);
    return 0;   
}

信息

递交者
类型
递交
题目
树的深度 T1
题目数据
下载
语言
C++
递交时间
2018-08-25 11:29:34
评测时间
2018-08-25 11:29:34
评测机
分数
30
总耗时
5544ms
峰值内存
23.535 MiB