제출 #889554

#제출 시각아이디문제언어결과실행 시간메모리
889554LeVanThuc동기화 (JOI13_synchronization)C++17
0 / 100
77 ms90408 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define fi first #define se second #define p(x,y) pair<ll,ll>(x,y) #define BIT(i,x) ((x>>i)&1) #define MASK(x) (1<<x) #define ld long double #define __builtin_popcount __builtin_popcountll #define pll pair<ll,ll> #define kt cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n" template<class T1,class T2> bool maximize(T1 &x,T2 y) { if(x<y) { x=y; return 1; } return 0; } template<class T1,class T2> bool minimize(T1 &x,T2 y) { if(y<x) { x=y; return 1; } return 0; } const ll M=1e9+9; template <class T1,class T2> void add(T1 &x,T2 y) { x+=y; if(x>=M) x-=M; } template <class T1,class T2> void sub(T1 &x, T2 y) { x-=y; if(x<0) x+=M; } void online() { std::ios_base::sync_with_stdio(0); cin.tie(0); #ifdef thuc freopen("input.inp","r",stdin); freopen("output.out","w",stdout); #else #endif // thuc } const ll N=200100; vector<ll> gr[N]; ll c[N],par[N][20],heavy[N],head[N],in[N],cnt,Tree[4*N],vl[N],lst[N],n,q,m; ll U[N],V[N]; void dfs(ll u) { c[u]=1; for(auto v:gr[u]) { if(v==par[u][0]) continue; par[v][0]=u; dfs(v); c[u]+=c[v]; if(c[heavy[u]]<c[v]) { heavy[u]=v; } } } void decompose(ll u,ll h) { head[u]=h; in[u]=++cnt; if(heavy[u]) { decompose(heavy[u],h); } for(auto v:gr[u]) { if(v==par[u][0]||v==heavy[u]) continue; decompose(v,v); } } ll update(ll i,ll l,ll r,ll pos,ll vl) { if(r<pos||pos<l) return Tree[i]; if(l==r) return Tree[i]=vl; return Tree[i]=update(i*2,l,(l+r)/2,pos,vl)&update(i*2+1,(l+r)/2+1,r,pos,vl); } ll query(ll i,ll l,ll r,ll l1,ll r1) { if(r1<l||r<l1) return 1; if(l1<=l&&r<=r1) return Tree[i]; return query(i*2,l,(l+r)/2,l1,r1)&query(i*2+1,(l+r)/2+1,r,l1,r1); } ll root(ll u) { while(u!=1) { if(!query(1,1,n,in[head[u]],in[u])) break; u=par[head[u]][0]; } for(int i=18;i>=0;i--) { if(head[par[u][i]]==head[u]) { if(query(1,1,n,in[par[u][i]],in[u])) u=par[par[u][i]][0]; } } if(query(1,1,n,in[u],in[u])) u=par[u][0]; return u; } ll change(ll i) { ll u=root(U[i]),v=root(V[i]); if(v==V[i]) { update(1,1,n,in[v],1); vl[u]=vl[v]+vl[u]-lst[i]; } else { update(1,1,n,in[V[i]],0); lst[i]=vl[u]; vl[root(V[i])]=vl[u]; } } int main() { online(); cin>>n>>m>>q; for(int i=1;i<n;i++) { ll u,v; cin>>u>>v; U[i]=u; V[i]=v; gr[u].emplace_back(v); gr[v].emplace_back(u); } dfs(1); decompose(1,1); for(int i=1;i<n;i++) { if(V[i]==par[U[i]][0]) { swap(U[i],V[i]); } } for(int i=1;i<=18;i++) { for(int j=1;j<=n;j++) { par[j][i]=par[par[j][i-1]][i-1]; } } for(int i=1;i<=n;i++) { vl[i]=1; } for(int i=1;i<=m;i++) { ll x; cin>>x; change(x); } for(int i=1;i<=q;i++) { ll u; cin>>u; cout<<vl[root(u)]<<'\n'; } kt; }

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

synchronization.cpp: In function 'long long int change(long long int)':
synchronization.cpp:132:1: warning: no return statement in function returning non-void [-Wreturn-type]
  132 | }
      | ^
#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...