제출 #151963

#제출 시각아이디문제언어결과실행 시간메모리
151963TadijaSebez동기화 (JOI13_synchronization)C++11
0 / 100
8100 ms28228 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back const int N=100050; int go[N][2],fa[N]; int pd(int x){ return go[fa[x]][0]==x?0:go[fa[x]][1]==x?1:-1;} void rot(int x) { int y=fa[x],z=fa[y],p=pd(x),q=pd(y),w=go[x][p^1]; if(z) go[z][q]=x;go[x][p^1]=y;go[y][p]=w; if(w) fa[w]=y;fa[x]=z;fa[y]=x; } void splay(int x){ while(pd(x)!=-1){ if(pd(fa[x])!=-1) rot(pd(fa[x])==pd(x)?fa[x]:x);rot(x);}} void access(int x){ for(splay(x),go[x][1]=0;fa[x];rot(x)) splay(fa[x]),go[fa[x]][1]=x;} int rt(int x){ access(x);while(go[x][0]) x=go[x][0];splay(x);return x;} const int M=2*N; int ans[N],last[N],u[N],v[N],dep[N],st[N]; vector<int> E[N]; void DFS(int u, int p){ ans[u]=1;dep[u]=dep[p]+1;for(int v:E[u]) if(v!=p) DFS(v,u);} int main() { int n,m,q; scanf("%i %i %i",&n,&m,&q); for(int i=1;i<n;i++) scanf("%i %i",&u[i],&v[i]),E[u[i]].pb(v[i]),E[v[i]].pb(u[i]); DFS(1,0); for(int i=1,d;i<=m;i++) { scanf("%i",&d); int a=u[d],b=v[d]; if(dep[a]<dep[b]) swap(a,b); if(st[d]) { int r=rt(b); last[a]=ans[a]=ans[r]; splay(a); assert(fa[a]==b); fa[a]=0; } else { int r=rt(b); ans[r]+=ans[a]-last[a]; splay(a); assert(fa[a]==0); fa[a]=b; } st[d]^=1; } for(int x;q--;) scanf("%i",&x),printf("%i\n",ans[rt(x)]); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

synchronization.cpp: In function 'void rot(int)':
synchronization.cpp:10:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(z) go[z][q]=x;go[x][p^1]=y;go[y][p]=w;
  ^~
synchronization.cpp:10:19: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(z) go[z][q]=x;go[x][p^1]=y;go[y][p]=w;
                   ^~
synchronization.cpp:11:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(w) fa[w]=y;fa[x]=z;fa[y]=x;
  ^~
synchronization.cpp:11:16: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(w) fa[w]=y;fa[x]=z;fa[y]=x;
                ^~
synchronization.cpp: In function 'int main()':
synchronization.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i",&n,&m,&q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:24:66: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<n;i++) scanf("%i %i",&u[i],&v[i]),E[u[i]].pb(v[i]),E[v[i]].pb(u[i]);
                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
synchronization.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i",&d);
   ~~~~~^~~~~~~~~
synchronization.cpp:49:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int x;q--;) scanf("%i",&x),printf("%i\n",ans[rt(x)]);
                  ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#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...