Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
decomposition
//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include <bits/stdc++.h> #define mp make_pair #define pb push_back using namespace std; typedef long long int ll; #define pii pair<ll, ll> struct node{ int val, ind; node() : val(-1e6), ind(-1e6){} node(int v, int i) : val(v), ind(i){} bool operator < (const node& rhs) const{ if(val == rhs.val) return ind > rhs.ind; return val > rhs.val; } bool operator == (const node& rhs) const{ return (rhs.val == val && ind == rhs.ind); } }; int mapIt[28][200001]; struct seg_tree{ node *seg; int n; seg_tree(int x, const vector<node>& v) : n(x-1){ seg = new node[4*n+1]; build(0, n, 0, v); } void build(int l, int r, int i, const vector<node>& v){ if(l == r){ seg[i] = v[l]; return; } int mid = (l+r)/2; build(l, mid, i*2+1, v); build(mid+1, r, i*2+2, v); seg[i] = min(seg[i*2+1], seg[i*2+2]); } void update(int l, int r, int i, int pos, const node& v){ if(l == r){ seg[i] = v; return; } int mid = (l+r)/2; if(mid >= pos) update(l, mid, i*2+1, pos, v); else update(mid+1, r, i*2+2, pos, v); seg[i] = min(seg[i*2+1], seg[i*2+2]); } void update(int p, const node& v){ update(0, n, 0, p, v); } node query(int l, int r, int i, int x, int y){ if(r < x || l > y) return node(); if(l >= x && r <= y) return seg[i]; int mid = (l+r)/2; return min(query(l, mid, i*2+1, x, y), query(mid+1, r, i*2+2, x, y)); } node query(int l, int r){ return query(0, n, 0, l, r); } void print(){ for(int j = 0; j <= n; j++){ node cur = query(0, n, 0, j, j); cout << "(" << cur.val << " " << cur.ind << ") "; } cout << endl; } }; struct node2{ multiset<node> v; void add(node t){ v.insert(t); } void rmv(node t){ v.erase(v.find(t)); } }; set<int> g[200001]; int n = 0, level[200001] = {0}, dp[28][200001], root, sub[200001], color[200001] = {0}; int dist[28][200001], lvl2[200001], par2[200001], parBranch[200001], sub2[200001] = {0}, st[200001], ed[200001]; vector<int> below[200001]; seg_tree *agg[200001]; int dfs(int src, int par){ level[src] = level[par] + 1; dp[0][src] = par; for(int j = 1; j < 28; j++) dp[j][src] = dp[j-1][dp[j-1][src]]; sub[src] = 1; for(auto it : g[src]) if(it != par) sub[src] += dfs(it, src); return sub[src]; } int dfsCentroid(int src, int par, int up, int tot){ for(auto it : g[src]) if(it != par && sub[it] > (tot/2)) return dfsCentroid(it, src, tot - sub[it], tot); return src; } int dfsArrange(int src, int par){ sub[src] = 1; for(auto it : g[src]) if(it != par) sub[src] += dfsArrange(it, src); return sub[src]; } void decompose(int src){ const set<int> t = g[src]; for(auto it : t){ g[src].erase(it); g[it].erase(src); int centroid = dfsCentroid(it, src, 0, sub[it]); g[src].insert(centroid); dfsArrange(centroid, src); decompose(centroid); } } int LCA(int u, int v){ if(level[u] > level[v]) swap(u, v); int dif = level[v] - level[u]; for(int j = 27; j >= 0; j--) if(dif >= (1 << j)){ dif -= (1 << j); v = dp[j][v]; } if(u == v) return u; for(int j = 27; j >= 0; j--) if(dp[j][v] != dp[j][u]) u = dp[j][u], v = dp[j][v]; return dp[0][v]; } int calcDist(int u, int v){ int lca = LCA(u, v); return (level[u] + level[v] - 2*level[lca]); } void dfsLast(int src, int par){ below[src].pb(src); par2[src] = par; sub2[src] = 1; lvl2[src] = lvl2[par] + 1; dist[lvl2[src]][src] = 0; int ind = 1; for(auto it : g[src]){ int cur = src; while(cur != 0){ dist[lvl2[cur]][it] = calcDist(it, cur); cur = par2[cur]; } dfsLast(it, src); for(auto i : below[it]) below[src].pb(i); st[it] = ind; ed[it] = ind + sub2[it] - 1; ind += sub2[it]; sub2[src] += sub2[it]; } vector<node> v; for(int j = 0; j < (int)below[src].size(); j++){ //cout << src << " " << below[src][j] << endl; mapIt[lvl2[src]][below[src][j]] = j; v.pb(node(dist[lvl2[src]][below[src][j]], below[src][j])); } agg[src] = new seg_tree(below[src].size(), v); } void print(int src, int par){ cout << src << " " << par << endl; for(auto it : g[src]) print(it, src); } void decomposeTree(){ dfs(1, 0); root = dfsCentroid(1, 0, 0, n); dfs(root, 0); decompose(root); //print(root, 0); dfsLast(root, 0); } void add(int src){ int cur = src, dis = 0, branch = 0; while(cur != 0){ agg[cur] -> update(mapIt[lvl2[cur]][src], node(dis, src)); cur = par2[cur]; dis = dist[lvl2[cur]][src]; } } void rmv(int src){ int cur = src, dis = 0, branch = 0; while(cur != 0){ agg[cur] -> update(mapIt[lvl2[cur]][src], node(-1e6, -1e6)); cur = par2[cur]; dis = dist[lvl2[cur]][src]; } } void print(multiset<node> m){ for(auto it : m) cout << "(" << it.val << " " << it.ind << ") "; cout << endl; } void print(){ cout << "\n\nagg : \n"; for(int i = 1; i <= n; i++) agg[i] -> print(); } int query(int src){ int cur = src, l = n+1, r = n+1, dis = 0; node ans; while(cur != 0){ int lft = 0, rgt = sub2[cur] - 1; node t; if(l > 0){ t = agg[cur] -> query(lft, l-1); t.val += dis; ans = min(ans, t); } if(r+1 <= rgt){ t = agg[cur] -> query(r+1, rgt); t.val += dis; ans = min(ans, t); } l = st[cur]; r = ed[cur]; cur = par2[cur]; dis = dist[lvl2[cur]][src]; } return ans.ind; } void initialize(){ for(int j = 0; j <= n; j++){ agg[j] = NULL; //info[j].clear(); below[j].clear(); g[j].clear(); level[j] = 0; lvl2[j] = 0; color[j] = 0; } } int main(){ ios_base :: sync_with_stdio(0); cin.tie(0); int t; scanf("%d",&t); while(t--){ initialize(); int m = 200000; n = 200000; scanf("%d %d",&n ,&m); for(int j = 2; j <= n; j++){ int x = j-1; scanf("%d",&x); g[x].insert(j); g[j].insert(x); } decomposeTree(); //print(); while(m--){ int x = (m * 2 + 100*3) % n, fg = 1; if(x == 0) x = m; scanf("%d",&x); if(color[x]) add(x), fg = 0; printf("%d\n",query(x)); if(fg) rmv(x); color[x] ^= 1; //print(); } } return 0; }
run
|
edit
|
history
|
help
0
single_digit
HeapSort
Buenos Amigos
numberOftweets
IndiSort
cvcvcvcvv
Ss
Interest Compounding
Shultz_Lab2.CPP
Memory_test