제출 #888868

#제출 시각아이디문제언어결과실행 시간메모리
888868ByeWorld동기화 (JOI13_synchronization)C++14
50 / 100
8048 ms23944 KiB
#include <bits/stdc++.h> #define bupol __builtin_popcount //#define int long long #define ll long long #define ld long double #define fi first #define se second #define pb push_back #define lf (id<<1) #define rg ((id<<1)|1) #define md ((l+r)>>1) using namespace std; const int MAXN = 1e5+20; const int MAXA = 2e5+10; const int LOG = 19; typedef pair<int,int> pii; typedef pair<pii,int> ipii; int n, m, q; int u[MAXN], v[MAXN]; vector <int> adj[MAXN]; int par[MAXN], sub[MAXN], dep[MAXN], idx[MAXN]; int root[MAXN]; vector <int> ch[MAXN]; //isi chain bool ty[MAXA]; struct node { vector<int> bit; int siz; //build void bd(int x){ siz = 2*x; bit.resize(2*x+5); } // que int que(int x){ // mulai dari idx dep[x], cari ke atas yg duluan 1 int dp = dep[x]-dep[root[x]]+1; int te = 0; // value suffix for(int i=dp; i>=1; i-=i&(-i)) te += bit[i]; //cout << te << ' ' << x << " te\n"; if(te==0) return -1; // gk ketemu //cout << " pp\n"; // skrg cari te-1 int ret = 0, sum = 0; for(int i=LOG-1; i>=0; i--){ if(ret + (1<<i) <= siz && sum+bit[ret+(1<<i)] <= te-1){ sum += bit[ret+(1<<i)]; ret += (1<<i); } } // ret+1 --> depth dr yg valnya 1 //cout << ids << " ids\n"; return ch[root[x]][ret]; // idx yg valuenya 1 } // upd void upd(int x, int y){ // depth dr idx = x x = x-dep[root[x]]+1; for(int i=x; i<=siz; i+=i&(-i)) bit[i] += y; } } *st[MAXN]; int query(int x){ // x --> idx nya while(st[x]->que(x) == -1){ x = par[root[x]]; } // udh ketemu return st[x]->que(x); // idxnya } void update(int x, int nw){ // idx x += nw st[x]->upd(dep[x], nw); } void dfs(int nw, int pa){ par[nw] = pa; sub[nw] = 1; dep[nw] = dep[pa]+1; for(auto nx : adj[nw]){ if(nx == pa) continue; dfs(nx, nw); sub[nw] += sub[nx]; } } void build(int x, int y){ st[x] = new node(); st[x]->bd(dep[y]-dep[x]+1); for(int i=dep[x]+1; i<=dep[y]; i++) st[idx[i]] = st[x]; } int val[MAXN], up[MAXN]; signed main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> m >> q; for(int i=1; i<=n-1; i++){ cin >> u[i] >> v[i]; adj[u[i]].pb(v[i]); adj[v[i]].pb(u[i]); } dfs(1, 0); for(int i=1; i<=n-1; i++){ if(dep[u[i]] > dep[v[i]]) swap(u[i], v[i]); } vector <int> qu; qu.pb(1); sub[n+1] = -1; while(!qu.empty()){ int nw = qu.back(); int tp = nw; qu.pop_back(); while(true){ ch[tp].pb(nw); root[nw] = tp; idx[dep[nw]] = nw; int big = n+1; for(auto nx : adj[nw]){ if(nx==par[nw]) continue; if(sub[nx] > sub[big]) big = nx; } if(big==n+1) break; for(auto nx : adj[nw]){ if(nx==par[nw] || nx==big) continue; qu.pb(nx); } nw = big; } build(tp, nw); } for(int i=1; i<=n; i++){ update(i, 1); val[i] = 1; up[i] = 0; } for(int i=1; i<=m; i++){ int x; cin >> x; //cout << u[x] << ' ' << v[x] << " atas\n"; ty[x] ^= 1; if(ty[x]){ // ke nyala, join update(v[x], -1); //yg bawah int idx = query(u[x]); val[idx] = val[idx]+val[v[x]]-up[v[x]]; } else { // ke mati int idx = query(v[x]); //cout << i << ' ' << x << ' ' << idx << " idx\n"; update(v[x], 1); val[v[x]] = val[idx]; up[v[x]] = val[idx]; } // for(int j=1; j<=n; j++){ // cout << j << ' '<< val[j] << ' ' << up[j] << " up\n"; // } } while(q--){ int x; cin >> x; int anc = query(x); cout << val[anc] << '\n'; //cout << anc << ' ' << " anc\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...