Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
各位大神帮忙看一下为什么 总是MLE啊 谢谢了#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=10005; int tme,n; int cnt; int root; int in[N]; int fa[N][17],deep[N]; struct node { int net; int to; }e[2*N]; int head[N]; void add (int a,int b) { cnt++; e[cnt].to=b; e[cnt].net=head[a]; head[a]=cnt; } void dfs(int x,int pre,int step) { fa[x][0]=pre;deep[x]=step; for(int i=head[x];i;i=e[i].net) { int t=e[i].to; dfs(t,x,step+1); } } int lca(int x,int y) { int re; if(deep[x]<deep[y]) swap(x,y); for(int i=16;i>=0;i--) { if(deep[fa[x][i]]>=deep[y]) x=fa[x][i]; } if(x==y) return x; for(int i=16;i>=0;i--) { if(fa[x][i]!=fa[y][i]) { x=fa[x][i]; y=fa[x][i]; } else re=fa[x][i]; } return re; } int main() { scanf("%d",&tme); while(tme--) { memset(head,0,sizeof(head)); memset(fa,0,sizeof(fa)); memset(in,0,sizeof(in)); memset(deep,0,sizeof(deep)); scanf("%d",&n); for(int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); add(x,y); in[y]++; } for(int i=1;i<=n;i++) { if(in[i]==0) { root=i; break; } } dfs(root,root,1); for(int j=1;j<=16;j++) { for(int i=1;i<=n;i++) { fa[i][j]=fa[fa[i][j-1]][j-1]; } } int c,d; scanf("%d%d",&c,&d); int ans=lca(c,d); printf("%d\n",ans); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator