Submission #14622

#TimeUsernameProblemLanguageResultExecution timeMemory
14622dohyun0324Synchronization (JOI13_synchronization)C++98
0 / 100
1002 ms25248 KiB
#include<stdio.h> #include<vector> #include<algorithm> #include<string.h> #include<math.h> using namespace std; typedef pair<int,int> ppair; vector<ppair>con[200010]; int ch3[200010],val2,dap[200010],pos[200010],w2,en[200010],counter[400010],val,cnt,p[400010],num[500],t,n,m,q,c,w,arr[500],save[400010],arr2[500],group[200010],ch[200010],ch2[200010]; struct data{ int x,y; }e[200010]; void dfs2(int x) { int i; ch2[x]=1; group[x]=val; dap[x]=val2; for(i=0;i<con[x].size();i++){ if(ch[con[x][i].second]==1 && ch2[con[x][i].first]==0) dfs2(con[x][i].first); } } void pro() { memset(ch3,0,sizeof ch3); int i,j,s1,e1,x1,x2,k=0,p1,p2; for(i=1;i<=w;i++) { ch[arr[i]]=!ch[arr[i]]; x1=group[p[arr[i]*2]]; x2=group[p[arr[i]*2+1]]; p1=dap[p[arr[i]*2+1]]; p2=dap[p[arr[i]*2]]; s1=num[p[arr[i]*2]]; e1=en[p[arr[i]*2]]; if(ch[arr[i]]==0) cnt++; for(j=1;j<=w2;j++) { if(s1<=num[arr2[j]] && num[arr2[j]]<=e1 && group[arr2[j]]==x1) { if(ch[arr[i]]) group[arr2[j]]=x2, dap[arr2[j]]+=(p1-save[arr[i]*2+1]); else group[arr2[j]]=cnt, save[arr[i]*2]=dap[arr2[j]]; } if(!(s1<=num[arr2[j]] && num[arr2[j]]<=e1) && group[arr2[j]]==x2) { if(ch[arr[i]]) dap[arr2[j]]+=(p2-save[arr[i]*2]); else save[arr[i]*2+1]=dap[arr2[j]]; } } } memset(ch2,0,sizeof ch2); memset(counter,0,sizeof counter); for(i=1;i<=w2;i++){ val=group[arr2[i]]; val2=dap[arr2[i]]; if(ch2[arr2[i]]==0) dfs2(arr2[i]); } for(i=1;i<=n;i++) counter[group[i]]=1; for(i=1;i<=n;i++) if(counter[i]) pos[i]=++k; cnt=k; for(i=1;i<=n;i++) group[i]=pos[group[i]]; } void dfs(int x) { int i; num[x]=++t; ch2[x]=1; for(i=0;i<con[x].size();i++){ if(ch2[con[x][i].first]) continue; p[con[x][i].second*2]=con[x][i].first; p[con[x][i].second*2+1]=x; dfs(con[x][i].first); } en[x]=t; } int main() { int i,x; scanf("%d %d %d",&n,&m,&q); for(i=1;i<=n;i++) group[i]=i, dap[i]=1; for(i=1;i<=n-1;i++){ scanf("%d %d",&e[i].x,&e[i].y); con[e[i].x].push_back(make_pair(e[i].y,i)); con[e[i].y].push_back(make_pair(e[i].x,i)); } dfs(1); c=sqrt(m); for(i=1;i<=m;i++){ scanf("%d",&arr[++w]); if(ch3[e[arr[w]].x]==0) arr2[++w2]=e[arr[w]].x, ch3[e[arr[w]].x]=1; if(ch3[e[arr[w]].y]==0) arr2[++w2]=e[arr[w]].y, ch3[e[arr[w]].y]=1; if(i%c==0 || i==m) pro(), w=0, w2=0; } for(i=1;i<=q;i++){ scanf("%d",&x); printf("%d\n",dap[x]); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...