Submission #877720

#TimeUsernameProblemLanguageResultExecution timeMemory
877720hafoSynchronization (JOI13_synchronization)C++14
100 / 100
326 ms37008 KiB
#include <bits/stdc++.h> #define ll long long #define ull unsigned ll #define pb push_back #define pa pair<int, int> #define pall pair<ll, int> #define fi first #define se second #define TASK "test" #define Size(x) (int) x.size() #define all(x) x.begin(), x.end() using namespace std; template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;} template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;} const int MOD = 1e9 + 7; const int LOG = 20; const int maxn = 2e5 + 7; const ll oo = 1e18 + 69; int n, m, q, u, v, x, st[maxn], en[maxn], timer = 0, cnt[maxn], last[maxn]; vector<int> g[maxn]; pa ed[maxn]; bool active[maxn]; struct BIT { int bit[maxn]; void update(int x, int val) { for(; x <= n; x += x&-x) bit[x] += val; } int get(int x) { int ans = 0; for(; x; x -= x&-x) ans += bit[x]; return ans; } } bit; struct LCA { int p[LOG][maxn], dep[maxn]; void dfs(int u, int par) { p[0][u] = par; for(auto v:g[u]) { if(v == par) continue; dep[v] = dep[u] + 1; dfs(v, u); } } void init() { dep[1] = 0; dfs(1, 0); for(int i = 1; i < LOG; i++) { for(int u = 1; u <= n; u++) p[i][u] = p[i - 1][p[i - 1][u]]; } } int find_nxt(int u) { for(int i = LOG - 1; i >= 0; i--) { if(p[i][u] == 0) continue; if(bit.get(st[p[i][u]]) == bit.get(st[u])) u = p[i][u]; } return u; } } lca; void dfs(int u, int par) { st[u] = ++timer; for(auto v:g[u]) { if(v == par) continue; dfs(v, u); } en[u] = timer; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); //freopen(TASK".inp", "r", stdin); //freopen(TASK".out", "w", stdout); cin>>n>>m>>q; for(int i = 1; i < n; i++) { cin>>ed[i].fi>>ed[i].se; g[ed[i].fi].pb(ed[i].se); g[ed[i].se].pb(ed[i].fi); } dfs(1, 0); lca.init(); for(int i = 1; i <= n; i++) { cnt[i] = 1; bit.update(st[i], -1); bit.update(en[i] + 1, 1); } while(m--) { cin>>x; u = ed[x].fi, v = ed[x].se; if(st[u] > st[v]) swap(u, v); if(active[x]) { cnt[v] = last[v] = cnt[lca.find_nxt(u)]; bit.update(st[v], -1); bit.update(en[v] + 1, 1); } else { bit.update(st[v], 1); bit.update(en[v] + 1, -1); cnt[lca.find_nxt(u)] += cnt[v] - last[v]; } active[x] ^= 1; } while(q--) { cin>>x; cout<<cnt[lca.find_nxt(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...