Submission #1244562

#TimeUsernameProblemLanguageResultExecution timeMemory
1244562tvgkSynchronization (JOI13_synchronization)C++20
100 / 100
216 ms29612 KiB
#include<bits/stdc++.h> using namespace std; #define task "a" #define se second #define fi first #define ll long long #define ii pair<ll, ll> const long mxN = 2e5 + 7; int in[mxN], out[mxN], num, n, m, q, u[mxN], v[mxN], bit[mxN], par[mxN][30], mem[mxN], ans[mxN]; vector<int> w[mxN]; void Upd(int j, int val) { while (j <= n) { bit[j] += val; j += j & (-j); } } int Get(int j) { int res = 0; while (j > 0) { res += bit[j]; j -= j & (-j); } return res; } void DFS(int j) { in[j] = ++num; for (int i = 1; i <= 20; i++) par[j][i] = par[par[j][i - 1]][i - 1]; for (int i : w[j]) { if (in[i]) continue; par[i][0] = j; DFS(i); } out[j] = num + 1; Upd(in[j], 1); Upd(out[j], -1); } int Find(int j) { int tmp = Get(in[j]); for (int i = 20; i >= 0; i--) { if (Get(in[par[j][i]]) == tmp) j = par[j][i]; } return j; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); //freopen(task".INP", "r", stdin); //freopen(task".OUT", "w", stdout); cin >> n >> m >> q; for (int i = 1; i < n; i++) { cin >> u[i] >> v[i]; w[u[i]].push_back(v[i]); w[v[i]].push_back(u[i]); } DFS(1); for (int i = 1; i <= n; i++) ans[i] = 1; for (int i = 1; i < n; i++) { if (par[u[i]][0] == v[i]) swap(u[i], v[i]); } for (int i = 1; i <= m; i++) { int id; cin >> id; int root = Find(u[id]); if (mem[id] == -1) { Upd(in[v[id]], 1); Upd(out[v[id]], -1); mem[id] = ans[v[id]] = ans[root]; } else { Upd(in[v[id]], -1); Upd(out[v[id]], 1); ans[v[id]] = ans[root] = ans[v[id]] + ans[root] - mem[id]; mem[id] = -1; } } for (int i = 1; i <= q; i++) { int tmp; cin >> tmp; cout << ans[Find(tmp)] << '\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...