제출 #1320816

#제출 시각아이디문제언어결과실행 시간메모리
1320816ppmn_6동기화 (JOI13_synchronization)C++20
100 / 100
201 ms37544 KiB
#include "bits/stdc++.h" using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); // https://codeforces.com/blog/entry/79148 class Timer: chrono::high_resolution_clock { const time_point start_time; public: Timer(): start_time(now()) {} rep elapsed_time() const { return chrono::duration_cast<chrono::milliseconds>(now() - start_time).count(); } } timer; struct FenwickTree { int n; vector<int> tree; FenwickTree(int n_) { n = n_; tree.resize(n + 1, 0); } void update(int p, int k) { while (p <= n) { tree[p] += k; p += p & (-p); } } int prefixQuery(int r) { int res = 0; while (r) { res += tree[r]; r -= r & (-r); } return res; } int query(int l, int r) { return prefixQuery(r) - prefixQuery(l - 1); } }; int main() { cin.tie(0); ios::sync_with_stdio(0); int n, q1, q2; cin >> n >> q1 >> q2; vector<vector<int>> tree(n + 1); vector<pair<int, int>> edges(n); for (int i = 1; i < n; i++) { auto &[u, v] = edges[i]; cin >> u >> v; tree[u].push_back(v); tree[v].push_back(u); } FenwickTree fwt(n + 1); vector<vector<int>> up(n + 1); vector<int> dist(n + 1), first(n + 1), last(n + 1); dist[0] = -1; int idx = 1; auto dfs = [&] (auto self, int c, int p)->void { dist[c] = dist[p] + 1; first[c] = idx; if (p) { int cur = 0, u = p; while (true) { up[c].push_back(u); if (cur >= up[u].size()) { break; } u = up[u][cur]; cur++; } } for (auto &v : tree[c]) { if (v != p) { idx++; self(self, v, c); } } last[c] = idx; }; dfs(dfs, 1, 0); vector<int> info(n + 1, 1), dupe(n + 1, 0); vector<bool> on(n + 1, 0); auto par = [&] (auto self, int c)->int { if (!on[c]) { return c; } int diff = dist[c] - fwt.prefixQuery(first[c]); for (int i = 1; i < up[c].size(); i++) { if (dist[up[c][i]] - fwt.prefixQuery(first[up[c][i]]) < diff) { return self(self, up[c][i - 1]); } } return self(self, up[c].back()); }; while (q1--) { int x; cin >> x; auto &[u, v] = edges[x]; if (dist[u] < dist[v]) { swap(u, v); } if (!on[u]) { info[par(par, v)] += info[u] - dupe[u]; fwt.update(first[u], 1); fwt.update(last[u] + 1, -1); } else { info[u] = dupe[u] = info[par(par, u)]; fwt.update(first[u], -1); fwt.update(last[u] + 1, 1); } on[u] = !on[u]; } while (q2--) { int u; cin >> u; cout << info[par(par, 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...