Submission #52596

#TimeUsernameProblemLanguageResultExecution timeMemory
52596SmelskiySynchronization (JOI13_synchronization)C++14
100 / 100
275 ms15220 KiB
#include <bits/stdc++.h> using namespace std; int timer; int x,y,xx,yy; int n,m,qq; int tin[100005]; int tout[100005]; vector<int> v[100005]; int sz; int res[100005]; int last[100005]; pair<int,int> a[100005]; int cnt[200005]; int t[600006]; int poc[600006]; void dfs(int x,int y) { tin[x]=++timer; poc[timer]=x; for (int i=0;i<v[x].size();++i) { int to=v[x][i]; if (to!=y) dfs(to,x); } tout[x]=timer; } int get(int l,int r,int x,int y) { if (t[x]<y || l>y) return -1; if (l==r) return poc[l]; int mid=(l+r)>>1; int res=get(mid+1,r,x+x+1,y); if (res!=-1) return res; return get(l,mid,x+x,y); } void update(int x,int y) { x+=sz-1; t[x]=y; x>>=1; while (x) { t[x]=max(t[x+x],t[x+x+1]); x>>=1; } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>m>>qq; for (int i=1;i<n;++i) { cin>>x>>y; a[i]=make_pair(x,y); v[x].push_back(y); v[y].push_back(x); } dfs(1,0); for (int i=1;i<n;++i) { x=a[i].first; y=a[i].second; if (tin[x]>tin[y]) swap(a[i].first,a[i].second); } sz=1; while (sz<n) sz+=sz; for (int i=1;i<=n;++i) t[sz+i-1]=tout[poc[i]]; for (int i=sz-1;i>0;--i) t[i]=max(t[i+i],t[i+i+1]); for (int i=1;i<=n;++i) { res[i]=1; } for (int i=1;i<=m;++i) { cin>>xx; x=a[xx].first; y=a[xx].second; yy=get(1,sz,1,tin[x]); cnt[xx]^=1; if (cnt[xx]) { res[yy]+=res[y]-last[y]; update(tin[y],0); } else { res[y]=last[y]=res[yy]; update(tin[y],tout[y]); } } while (qq--) { cin>>x; x=get(1,sz,1,tin[x]); cout<<res[x]<<'\n'; } }

Compilation message (stderr)

synchronization.cpp: In function 'void dfs(int, int)':
synchronization.cpp:24:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[x].size();++i) {
                  ~^~~~~~~~~~~~
#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...