| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 995357 | vjudge1 | Synchronization (JOI13_synchronization) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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=2e5+5;
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;
}
}