Submission #1188257

#TimeUsernameProblemLanguageResultExecution timeMemory
1188257duckindogSynchronization (JOI13_synchronization)C++17
100 / 100
106 ms20808 KiB
#include <bits/stdc++.h> using namespace std; const int N = 200'000 + 10; int n, m, q; pair<int, int> edge[N]; vector<int> ad[N]; int sz[N]; void dfs(int u, int p = -1) { sz[u] = 1; for (int v : ad[u]) { if (v == p) continue; dfs(v, u); sz[u] += sz[v]; } } int head[N], par[N]; int st[N], ed[N], node[N], num; void hld(int u, int p = -1) { if (!head[u]) head[u] = u; st[u] = ++num; node[num] = u; sort(ad[u].begin(), ad[u].end(), [&](int a, int b) { return sz[a] > sz[b]; }); bool goHeavy = false; for (const auto& v : ad[u]) { if (v == p) continue; if (!goHeavy) goHeavy = true, head[v] = head[u]; par[v] = u; hld(v, u); } ed[u] = num; } namespace BIT { int bit[N]; inline void upd(int i, int x) { for (; i <= n; i += i & -i) bit[i] += x; } inline int que(int i) { int ret = 0; for (; i; i -= i & -i) ret += bit[i]; return ret; } inline int que(int l, int r) { return que(r) - que(l - 1); } } int root(int u) { while (u != 1) { int x = head[u]; if (st[u] - st[x] + 1 == BIT::que(st[x], st[u])) { u = par[head[u]]; continue; } int uSum = BIT::que(st[u]); int pos = 0, sum = 0; for (int i = 16; i >= 0; --i) { int nPos = pos + (1 << i), nSum = sum + BIT::bit[nPos]; if (nPos > st[u] || uSum - nSum == st[u] - nPos) continue; tie(pos, sum) = {nPos, nSum}; } return pos == st[u] ? node[pos] : node[pos + 1]; } return 1; } bool isCon[N]; int answer[N], cAnswer[N]; int32_t main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m >> q; for (int i = 1; i < n; ++i) { int u, v; cin >> u >> v; edge[i] = {u, v}; ad[u].push_back(v); ad[v].push_back(u); } dfs(1); hld(par[1] = 1); for (int i = 1; i < n; ++i) { auto& [u, v] = edge[i]; if (st[u] > st[v]) swap(u, v); } fill(answer + 1, answer + n + 1, 1); while (m--) { int idx; cin >> idx; auto [u, v] = edge[idx]; isCon[idx] ^= 1; if (isCon[idx]) { u = root(u); BIT::upd(st[v], 1); answer[u] = answer[u] + answer[v] - cAnswer[idx]; } else { BIT::upd(st[v], -1); u = root(u); answer[v] = cAnswer[idx] = answer[u]; } } while (q--) { int u; cin >> u; cout << answer[root(u)] << "\n"; } }
#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...