Submission #577945

#TimeUsernameProblemLanguageResultExecution timeMemory
577945HuySynchronization (JOI13_synchronization)C++17
100 / 100
560 ms27796 KiB
#include<bits/stdc++.h> //#define int long long #define pii pair<ll,ll> #define fi first #define se second using namespace std; using ll = long long; using ldb = long double; const int N = (int)5e5+2; const int maxN = (int)2e5 + 5; const int mod = 1e9 + 7; const ll infty = 1e18; void InputFile() { //freopen("scrivener.inp","r",stdin); //freopen("scrivener.out","w",stdout); //freopen("test.out","r",stdin); } void FastInput() { ios_base::sync_with_stdio(false); cin.tie(nullptr); } int n,m,q; vector<vector<int>> adj; int anc[25][maxN]; int lg[maxN]; int depth[maxN]; int TimeDFS = 0; int sta[maxN]; int fin[maxN]; int now[maxN]; int lst[maxN]; int x[maxN],y[maxN]; int apr[maxN]; void Prepare() { lg[1] = 0; for(int i = 2;i < maxN;i++) { lg[i] = lg[i/2] + 1; } } void Read() { cin >> n >> m >> q; adj.resize(n+1); for(int i = 1;i < n;i++) { int u,v; cin >> u >> v; x[i] = u; y[i] = v; adj[u].push_back(v); adj[v].push_back(u); } } int bit[maxN]; void Update(int idx,int val) { while(idx <= n) { bit[idx] += val; idx += (idx & (-idx)); } } void UpdRange(int l,int r,int val) { Update(l,val); Update(r+1,-val); } int Get(int idx) { if(idx == 0) return -1; int res = 0; while(idx > 0) { res += bit[idx]; idx -= (idx & (-idx)); } return res; } void preDFS(int u,int p) { sta[u] = ++TimeDFS; UpdRange(sta[u],sta[u],depth[u]+1); now[u] = 1; lst[u] = 0; for(int v : adj[u]) { if(v == p) continue; depth[v] = depth[u] + 1; anc[0][v] = u; for(int i = 1;i <= lg[n];i++) { anc[i][v] = anc[i-1][anc[i-1][v]]; } preDFS(v,u); } fin[u] = TimeDFS; } int Find(int u) { int comp = Get(sta[u]); for(int i = lg[n];i >= 0;i--) { if(Get(sta[anc[i][u]]) == Get(sta[u])) u = anc[i][u]; } return u; } void Solve() { Prepare(); preDFS(1,0); for(int i = 1;i <= m;i++) { int edg_id; cin >> edg_id; if(depth[x[edg_id]] > depth[y[edg_id]]) { swap(x[edg_id],y[edg_id]); } apr[edg_id]++; if(apr[edg_id]%2) { UpdRange(sta[y[edg_id]],fin[y[edg_id]],-1); int par = Find(y[edg_id]); now[par] += now[y[edg_id]] - lst[y[edg_id]]; now[y[edg_id]] = lst[y[edg_id]] = now[par]; } else { int par = Find(y[edg_id]); //now[par] += now[y[edg_id]] - lst[y[edg_id]]; now[y[edg_id]] = lst[y[edg_id]] = now[par]; UpdRange(sta[y[edg_id]],fin[y[edg_id]],1); } } //cout << sta[2] <<' '<< fin[2];return; //cout << Get(sta[3]);return; while(q--) { int u; cin >> u; int par = Find(u); cout << now[par] <<'\n'; } } void Debug() { //Main_sub(); //Naive(); } int32_t main() { FastInput(); //InputFile(); //int sub_type; //cin >> sub_type; //Sieve(); int test; //cin >> test; test = 1; while(test--) //for(int prc = 1; prc <= test; prc++) { Read(); Solve(); //Debug(); } } /* 13 1 769 514 336 173 181 373 519 338 985 709 729 702 168 12 581 */

Compilation message (stderr)

synchronization.cpp: In function 'int Find(int)':
synchronization.cpp:116:9: warning: unused variable 'comp' [-Wunused-variable]
  116 |     int comp = Get(sta[u]);
      |         ^~~~
#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...