Submission #208299

#TimeUsernameProblemLanguageResultExecution timeMemory
208299YJUSynchronization (JOI13_synchronization)C++14
100 / 100
417 ms41700 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pll; typedef long double ld; const ll MOD=1e9+7; const ll N=4e5+5; const ld pi=3.14159265359; const ll INF=(1LL<<62); #define REP(i,n) for(ll i=0;i<n;i++) #define REP1(i,n) for(ll i=1;i<=n;i++) #define pb push_back #define mp make_pair #define X first #define Y second #define setp setprecision #define lwb lower_bound #define SZ(a) (ll)a.size() ll n,x,y,m,q,bit[N],in[N],out[N],ti=1,lca[N][21],cd,ans[N],last[N],B[N]; vector<pll> edge; vector<ll> v[N]; void DFS(ll nd,ll pa){ lca[nd][0]=pa; in[nd]=ti++; ans[nd]=1; for(ll i=1;i<=20&&lca[nd][i-1];i++)lca[nd][i]=lca[lca[nd][i-1]][i-1]; for(auto i:v[nd]){ if(i==pa)continue; DFS(i,nd); } out[nd]=ti; } void mod(ll id,ll dx){ while(id<N)bit[id]+=dx,id+=(id&-id); } ll query(ll id){ ll tmp=0;while(id)tmp+=bit[id],id-=(id&-id);return tmp; } ll find(ll id){ ll tmp=id; for(ll i=20;i>=0;i--)if(lca[tmp][i]&&query(in[lca[tmp][i]])==query(in[id]))tmp=lca[tmp][i]; return tmp; } int main(){ ios_base::sync_with_stdio(0);cin.tie(0); cin>>n>>m>>q; REP(i,n-1){ cin>>x>>y; edge.pb(mp(x,y)); v[x].pb(y);v[y].pb(x); } DFS(1,0); REP1(i,n)mod(in[i],-1),mod(out[i],1); REP(i,m){ cin>>cd; y=edge[cd-1].Y;x=edge[cd-1].X; if(lca[y][0]==x)swap(x,y); if(B[cd-1]){ ans[x]=last[x]=ans[find(y)]; mod(in[x],-1),mod(out[x],1); }else{ ans[find(y)]+=ans[x]-last[x]; mod(in[x],1),mod(out[x],-1); } B[cd-1]=1-B[cd-1]; } while(q--)cin>>x,cout<<ans[find(x)]<<"\n"; return 0; }
#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...