Submission #984352

#TimeUsernameProblemLanguageResultExecution timeMemory
984352LOLOLOSynchronization (JOI13_synchronization)C++17
100 / 100
194 ms26088 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; #define f first #define s second #define pb push_back #define ep emplace #define eb emplace_back #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin()) #define mem(f,x) memset(f , x , sizeof(f)) #define sz(x) (int)(x).size() #define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b)) #define mxx *max_element #define mnn *min_element #define cntbit(x) __builtin_popcountll(x) #define len(x) (int)(x.length()) const int N = 1e5 + 10; vector <int> ed[N]; int p[N][20], f[N], in[N], ou[N], timer = 1, num[N], pr[N], used[N]; void upd(int i, int x) { for (; i < N; i += i & (-i)) f[i] += x; } int get(int i) { int s = 0; for (; i; i -= i & (-i)) s += f[i]; return s; } void dfs(int u, int v) { in[u] = timer++; p[u][0] = v; for (int j = 1; j < 20; j++) p[u][j] = p[p[u][j - 1]][j - 1]; for (auto x : ed[u]) { if (x == v) continue; dfs(x, u); } ou[u] = timer; upd(in[u], 1); upd(ou[u], -1); } int root(int x) { int v = get(in[x]); for (int j = 19; j >= 0; j--) { if (get(in[p[x][j]]) == v) x = p[x][j]; } return x; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m, q; cin >> n >> m >> q; vector <pair <int, int>> save; for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; ed[a].pb(b); ed[b].pb(a); save.pb({a, b}); } dfs(1, 1); for (int i = 1; i <= n; i++) { num[i] = 1; } for (int i = 1; i <= m; i++) { int id; cin >> id; id--; int a = save[id].f, b = save[id].s; if (p[a][0] == b) swap(a, b); if (used[id] == -1) { // remove edge int r = root(a); upd(in[b], 1); upd(ou[b], -1); num[b] = used[id] = num[r]; } else { // insert edge int r = root(a); upd(in[b], -1); upd(ou[b], 1); num[r] += abs(num[b] - used[id]); used[id] = -1; } } for (int i = 0; i < q; i++) { int x; cin >> x; cout << num[root(x)] << '\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...