제출 #470279

#제출 시각아이디문제언어결과실행 시간메모리
470279soroush동기화 (JOI13_synchronization)C++17
100 / 100
400 ms35396 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair < int, int > pii; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int maxn = 2e5 + 10; const int inf = 1e8 + 7; const int lg = 22; #define pb push_back #define endl '\n' #define dokme(x) cout << x, exit(0) #define ms(x, y) memset(x, y, sizeof x) int n, m, q, root, tim; int p[maxn], c[maxn], par[maxn][lg], st[maxn], ft[maxn]; int ans[maxn], lst[maxn], t[maxn]; ll fen[maxn]; int a[maxn]; bool mark[maxn], up[maxn]; vector < int > adj[maxn]; void dfs(int v) { st[v] = ++tim; for (int i: adj[v]) { if (p[i] == par[v][0]) continue; if (c[i] == v) swap(c[i], p[i]); par[c[i]][0] = v; dfs(c[i]); } ft[v] = tim; } void Add(int pos, int x) { for (; pos < maxn; pos += pos & -pos) fen[pos] += x; } void add(int l, int r, int x) { Add(l, x); Add(r + 1, -x); } int get(int pos) { int ans = 0; for (; pos; pos -= pos & -pos) ans += fen[pos]; return ans; } int getpar(int v) { int x = get(st[v]); for (int i = lg - 1; ~i; i--) if (par[v][i] && (1 << i) == x - get(st[par[v][i]])) v = par[v][i], x = get(st[v]); return v; } struct hld { int sz[maxn], st[maxn], ft[maxn], mx[maxn], h[maxn], tim, par[maxn], head[maxn]; int fen[maxn]; void dfs(int v, int p = 0) { h[v] = h[p] + 1; par[v] = p; st[v] = ++tim; sz[v] = 1; for (int i: adj[v]) if (c[i] ^ v) { dfs(c[i], v); if (sz[c[i]] >= sz[mx[v]]) mx[v] = c[i]; sz[v] += sz[c[i]]; } ft[v] = tim; } void hdfs(int v) { st[v] = ++tim; if (!head[v]) head[v] = v; if (mx[v]) head[mx[v]] = head[v], hdfs(mx[v]); for (int i: adj[v]) if (p[i] == v and c[i] ^ mx[v]) hdfs(c[i]); ft[v] = tim; } void add(int pos, int x) { for (; pos < maxn; pos += pos & -pos) fen[pos] += x; } void add(int l, int r, int x) { assert(l <= r); add(l, x); add(r + 1, -x); } int get(int v) { int ans = 0; for (v = st[v]; v; v -= v & -v) ans += fen[v]; return ans; } void padd(int u, int v, int x) { if (!x) return; while (head[u] ^ head[v]) { add(st[head[u]], st[u], x); u = par[head[u]]; } add(st[v], st[u], x); } } HLD; int32_t main() { cin.tie(0) -> sync_with_stdio(0); cin >> n >> m >> q; for (int i = 1; i < n; i++) { cin >> p[i] >> c[i]; adj[p[i]].pb(i); adj[c[i]].pb(i); } for (int i = 1; i <= m; i++) cin >> t[i], lst[t[i]] = i; root = 1; dfs(root); HLD.dfs(root); HLD.hdfs(root); for (int j = 1; j < lg; j++) for (int i = 1; i <= n; i++) par[i][j] = par[par[i][j - 1]][j - 1]; for (int i = 1; i <= n; i++) a[i] = 1, HLD.padd(i, i, 1); for (int i = 1; i <= m; i++) { mark[t[i]] ^= 1; int v = c[t[i]]; up[v] ^= 1; if (mark[t[i]]) { add(st[v], ft[v], 1); a[getpar(v)] += a[v]; HLD.padd(par[v][0], getpar(v), a[v]); a[v] = 0; } else { ans[v] = ans[getpar(v)] + HLD.get(getpar(v)) - HLD.get(v); add(st[v], ft[v], -1); } } for (int i = 1; i <= q; i++) { int v; cin >> v; cout << ans[getpar(v)] + HLD.get(getpar(v)) << endl; } 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...