Submission #1189415

#TimeUsernameProblemLanguageResultExecution timeMemory
1189415zNatsumiSynchronization (JOI13_synchronization)C++20
40 / 100
8092 ms16076 KiB
#include <bits/stdc++.h> using namespace std; using ii = pair<int, int>; const int N = 2e5 + 5; int n, m, q, in[N], out[N], timer, pa[N], res[N], pre[N]; bool status[N]; ii edge[N]; vector<int> ad[N]; void dfs(int u, int p){ in[u] = ++timer; for(auto v : ad[u]) if(v != p) dfs(v, u); out[u] = timer; } int root(int u){ while(pa[u] != u) u = pa[u]; return u; } int32_t main(){ cin.tie(0)->sync_with_stdio(0); // #define task "test" // if(fopen(task ".inp", "r")){ // freopen(task ".inp", "r", stdin); // freopen(task ".out", "w", stdout); // } cin >> n >> m >> q; for(int i = 1; i < n; i++){ int u, v; cin >> u >> v; ad[u].push_back(v); ad[v].push_back(u); edge[i] = {u, v}; } dfs(1, -1); for(int i = 1; i <= n; i++){ pa[i] = i; res[i] = 1; auto &[u, v] = edge[i]; if(in[u] > in[v]) swap(u, v); } while(m--){ int e; cin >> e; auto [u, v] = edge[e]; status[e] ^= 1; if(status[e]){ pa[v] = u; u = root(u); res[u] += res[v] - pre[e]; }else{ pa[v] = v; u = root(u); res[v] = pre[e] = res[u]; } } while(q--){ int u; cin >> u; cout << res[root(u)] << "\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...