Submission #995358

#TimeUsernameProblemLanguageResultExecution timeMemory
995358vjudge1Synchronization (JOI13_synchronization)C++17
0 / 100
184 ms262144 KiB
#include <bits/stdc++.h> #define rep(a,b,c) for(int a=b; a<c; a++) #define repa(a,b) for(auto a:b) #define ll long long #define pb push_back #define endl "\n" #define pii pair<int, int> #define fi first #define se second #define mid ((l+r)>>1) using namespace std; struct segtree{ segtree *left, *right; int l, r, v=0; segtree(int x, int y): l(x), r(y){ if(l==r) return; left = new segtree(l,mid); right= new segtree(mid+1,r); } void update(int x){ if(r<x || x<l) return; if(x<=l && r<=x){ v^=1; return; } left->update(x); right->update(x); v=((left->v)&(right->v)); } int query(int x, int y){ if(r<x || y<l) return 1; if(x<=l && r<=y) return v; return ((left->query(x,y))&(right->query(x,y))); } }; const int lim=1e5+1000; int sz[lim], tin[lim], root[lim], par[lim], hvy[lim], node[lim], timer; vector<int> adj[lim]; bitset<lim> vnode[lim]; segtree ST(0,lim); void sztree(int u, int p){ sz[u]=1; hvy[u]=lim-1; par[u]=p; repa(v,adj[u]){ if(v==p) continue; sztree(v,u); sz[u]+=sz[v]; if(sz[hvy[u]]<sz[v]) hvy[u]=v; } } void dfs_hld(int u, int p){ tin[u]=timer++; node[tin[u]]=u; repa(v,adj[u]){ if(v!=hvy[u]) continue; root[v]=root[u]; dfs_hld(v,u); } repa(v,adj[u]){ if(v==hvy[u] || v==p) continue; root[v]=v; dfs_hld(v,u); } } int query(int u){ while(ST.query(tin[root[u]],tin[u])) u=par[u]; //PINCHE BINARIA COMO NO ME SALGA ME PEGO UN TIRO int l, r; l=tin[root[u]],r=tin[u]; while(l<=r){ if(ST.query(mid,r)) r=mid-1; else l=mid+1; } if(r<tin[u]) return node[r]; else return u; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m, q, u, v; cin>>n>>m>>q; pii edges[n]; rep(i,1,n+1) vnode[i].set(i); rep(i,1,n){ cin>>u>>v; adj[u].pb(v); adj[v].pb(u); edges[i]={u,v}; } sztree(1,0); rep(i,1,n) if(par[edges[i].fi]!=edges[i].se) swap(edges[i].fi,edges[i].se); root[1]=1; dfs_hld(1,0); while(m--){ cin>>u; u=edges[u].fi; v=query(u); if(v!=u) vnode[u]|=vnode[v]; ST.update(tin[u]); v=query(u); if(v!=u) vnode[v]|=vnode[u]; } while(q--){ cin>>u; v=query(u); if(v!=u) vnode[u]|=vnode[v]; cout<<vnode[u].count()<<endl; } }
#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...