我晕,刚开始不知到怎么存数据,后来看了题解发现vector很神奇!
但是一看各位大神们都是用c++交的,G++交会TLE!最后自己套上输入外挂竟然AC了!才100ms+有木有!
太神奇了!这是我第一次用到输入外挂题目!
ps:以后我的代码风格使用松散加原味的代码,毕竟不能因为ACM而形成一股难以使用的代码习惯
code:
//从今天开始不再用宏定义 //采用松散的代码写法~~ #include <iostream> #include <algorithm> #include <cstdio> #include <vector> #include <cstring> using namespace std; const int maxn=20001; vector<int> g[maxn]; int in[maxn], out[maxn]; int dfs(int root){ if(out[root]==0) return root; vector<int> tmp; for(int i=0;i<out[root];i++) tmp.push_back(dfs(g[root][i])); sort(tmp.begin(),tmp.end()); return tmp[(out[root]+1)/2-1]; } char c; inline void scan(int &x){ while(c=getchar(),c<'0'||c>'9'); x=c-'0'; while(c=getchar(),c>='0'&&c<='9')x=x*10+c-'0'; } int main() { int N,tmp,i,j,root; while(~scanf("%d",&N)) { for(i=1;i<=N;i++) g[i].clear(); memset(in,0,sizeof(in)); for(i=1;i<=N;i++) { scan(out[i]); for(j=1;j<=out[i];j++) { scan(tmp); g[i].push_back(tmp); in[tmp]++; } } for(i=1;i<=N;i++) { if(in[i]==0) { root=i; break; } } printf("%d\n",dfs(root)); } return 0; }