제출 #1260431

#제출 시각아이디문제언어결과실행 시간메모리
1260431nlsosadSynchronization (JOI13_synchronization)C++20
100 / 100
216 ms45880 KiB
#include <bits/stdc++.h> using namespace std; vector<int> a[100001], tr[800001]; int depth[100001], state[100001], cnt[100001], f[100001], mx[100001], p[100001], r[100001]; pair<int, int> edge[100001]; vector<pair<int, int>> change; int find(int x){ if(p[x]==x){ return x; }else return find(p[x]); } void unite(int u, int v){ int ru = find(u), rv = find(v); if(ru!=rv){ change.push_back({ru, rv}); int tmp = mx[ru] + mx[rv] - f[v]; mx[ru] = mx[rv] = tmp; if(r[ru] > r[rv]){ p[rv] = ru; r[ru] += r[rv]; }else{ p[ru] = rv; r[rv] += r[ru]; } } } void undo(){ auto [u, v] = change.back(); change.pop_back(); int tmp = max(mx[u], mx[v]); mx[u] = mx[v] = tmp; if(r[u] > r[v]){ r[u]-=r[v]; }else r[v]-=r[u]; p[u] = u; p[v] = v; } void dfs(int u, int p){ for (int v:a[u]){ if(v!=p){ depth[v] = depth[u] + 1; dfs(v, u); } } } void add(int node, int start, int end, int l, int r, int id){ if(start > r or end < l){ return; } if(l<=start and end<=r){ tr[node].push_back(id); return; } int mid = (start+end)/2; add(2*node, start, mid, l, r, id); add(2*node+1, mid+1, end, l, r, id); } void query(int node, int start, int end){ for (int id:tr[node]){ auto [u, v] = edge[id]; if(depth[u] > depth[v])swap(u, v); unite(u, v); } if(start!=end){ int mid = (start+end)/2; query(2*node, start, mid); query(2*node+1, mid+1, end); } for (int id:tr[node]){ auto [u,v] = edge[id]; if(depth[u] > depth[v])swap(u,v); f[v] = mx[find(v)]; undo(); } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n, m, q; cin >> n >> m >> q; for (int i =1;i<n;++i){ int u, v; cin >> u >> v; edge[i] = {u, v}; a[u].push_back(v); a[v].push_back(u); } for (int i =1;i<=n;++i){ mx[i] = 1; r[i] = 1, p[i] = i; } dfs(1, 0); for (int i = 1;i<=m;++i){ int id; cin >> id; if(state[id]==0){ state[id] = i; }else{ add(1, 1, m, state[id], i-1, id); state[id] = 0; } } for (int i = 1;i<n;++i){ if(state[i]){ add(1, 1, m, state[i], m, i); state[i] = 0; } } query(1, 1, m); while(q--){ int u; cin >> u; cout << mx[find(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...