Submission #960886

#TimeUsernameProblemLanguageResultExecution timeMemory
960886pccSynchronization (JOI13_synchronization)C++17
30 / 100
211 ms68636 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> #define pii pair<int,int> #define fs first #define sc second #define tlll tuple<ll,ll,ll> const int mxn = 1e5+10; int bit[mxn]; pii eul[mxn],edges[mxn]; int N,M,Q; int dep[mxn]; vector<int> tree[mxn]; bitset<mxn> done; int mv[mxn*2]; int rt; int par[mxn][20]; int pt = 0; set<int> st[mxn]; void modify(int p,int v){ for(;p<mxn;p+=p&-p)bit[p] += v; return; } int getval(int p){ int re = 0; for(;p>0;p-= p&-p)re += bit[p]; return re; } void dfs(int now){ eul[now].fs = ++pt; for(int i = 1;i<20;i++)par[now][i] = par[par[now][i-1]][i-1]; for(auto nxt:tree[now]){ if(nxt == par[now][0])continue; par[nxt][0] = now; dep[nxt] = dep[now]+1; dfs(nxt); } eul[now].sc = pt; return; } void change(int p){ auto [a,b] = edges[p]; if(dep[a]>dep[b])swap(a,b); if(done[p]){ done[p] = false; modify(eul[b].fs,-1); modify(eul[b].sc+1,1); return; } done[p] = true; modify(eul[b].fs,1); modify(eul[b].sc+1,-1); int up = b; for(int i = 19;i>=0;i--){ if(getval(eul[b].fs)-getval(eul[par[up][i]].fs) == dep[b]-dep[par[up][i]])up = par[up][i]; } if(up == b)return; if(st[up].size()<st[b].size())st[up].swap(st[b]); for(auto &i:st[b])st[up].insert(i); st[b].clear(); return; } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>N>>M>>Q; for(int i = 1;i<N;i++){ auto &[a,b] = edges[i]; cin>>a>>b; tree[a].push_back(b); tree[b].push_back(a); } for(int i = 1;i<=M;i++)cin>>mv[i]; while(Q--){ cin>>rt; par[rt][0] = rt; dfs(rt); done.reset(); for(int i = 1;i<=N+1;i++)bit[i] = 0; for(int i = 1;i<=N;i++)st[i].clear(); for(int i = 1;i<=N;i++)st[i].insert(i); for(int i = 1;i<=M;i++)change(mv[i]); cout<<st[rt].size()<<'\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...