제출 #960460

#제출 시각아이디문제언어결과실행 시간메모리
960460starchanDynamic Diameter (CEOI19_diameter)C++17
49 / 100
5067 ms204784 KiB
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #define int long long #define in pair<int, int> #define f first #define s second #define pb push_back #define pob pop_back #define INF (int)1e17 #define fast() ios_base::sync_with_stdio(false); cin.tie(NULL) struct seg_tree { //range add range max. vector<int> tree, lazy; void init(int n) { tree.assign(4*n+2, 0); lazy.assign(4*n+2, 0); return; } void upd(int val, int ql, int qr, int id, int l, int r) { if(qr < l || r < ql) return; if(ql <= l && r <= qr) { tree[id]+=val; lazy[id]+=val; return; } int m = (l+r)/2; upd(val, ql, qr, 2*id, l, m); upd(val, ql, qr, 2*id+1, m+1, r); tree[id] = max(tree[2*id], tree[2*id+1])+lazy[id]; return; } int query(int ql, int qr, int id, int l, int r) { if(qr < l || r < ql) return 0; if(ql <= l && r <= qr) return tree[id]; int m = (l+r)/2; int s1 = query(ql, qr, 2*id, l, m); int s2 = query(ql, qr, 2*id+1, m+1, r); return max(s1, s2); } }; const int MX = 1e5+5; const int LOGM = 17; vector<in> adj[MX]; vector<seg_tree> work; int pa[LOGM][MX], tin[LOGM][MX], tout[LOGM][MX], just[LOGM][MX]; vector<pair<in, int>> edge; vector<bool> cut(MX); vector<int> sz(MX); int centh[MX], ctin[MX], ctout[MX]; int ans[MX];//ans[i] stores max path through vertex i, where i has least centh[i] set<in> ANS;//stores the above in a pair format (for efficient updates etc) set<in> help[MX];//stores the neighbour set per centroid vertex with maximum weights enabled. void dfs(int u, int p) { sz[u] = 1; for(auto [v, w]: adj[u]) { if(cut[v]) continue; if(v==p) continue; dfs(v, u); sz[u]+=sz[v]; } return; } int centroid(int u, int p, int SZ) { for(auto [v, w]: adj[u]) { if(cut[v]) continue; if(v==p) continue; if(2*sz[v] > SZ) return centroid(v, u, SZ); } return u; } int centimer; int centroid_decomposition(int u, int lvl) { dfs(u, 0); int root = centroid(u, 0, sz[u]); work[root].init(sz[u]); cut[root] = 1; centh[root] = lvl; ctin[root] = ++centimer; sz[root] = sz[u]; for(auto [v, w]: adj[root]) { if(cut[v]) continue; int X = centroid_decomposition(v, lvl+1); pa[0][X] = root; } ctout[root] = centimer; return root; } void cendfs(int u, int p, int root, int &timer) { tin[centh[u]-centh[root]][u] = ++timer; if((p != 0) && (p != root)) just[centh[u]-centh[root]][u] = just[centh[p]-centh[root]][p]; else { help[root].insert({0, u}); just[centh[u]-centh[root]][u] = u; } for(auto [v, w]: adj[u]) { if(v==p) continue; if((ctin[v] < ctin[root]) || (ctout[v] > ctout[root])) continue; cendfs(v, u, root, timer); } tout[centh[u]-centh[root]][u] = timer; return; } void update(int root, int u, int val) { int D = centh[u]-centh[root]; int J = just[D][u]; int D_p = centh[J]-centh[root]; int NUM = work[root].query(tin[D_p][J], tout[D_p][J], 1, 1, sz[root]); help[root].erase({NUM, J}); work[root].upd(val, tin[D][u], tout[D][u], 1, 1, sz[root]); NUM = work[root].query(tin[D_p][J], tout[D_p][J], 1, 1, sz[root]); help[root].insert({NUM, J}); return; } int upd(int i, int val) { auto [u, v] = edge[i].f; int delta = val-edge[i].s; edge[i] = {{u, v}, val}; int root = (centh[u] < centh[v])? u : v; while(root) { if(tin[centh[u]-centh[root]][u] < tin[centh[v]-centh[root]][v]) swap(u, v); update(root, u, delta); ANS.erase({ans[root], root}); ans[root] = 0; auto it = help[root].end(); it--; ans[root]+=((*it).f); it--; ans[root]+=((*it).f); ANS.insert({ans[root], root}); root = pa[0][root]; } auto itt = ANS.end(); itt--; return (*itt).f; } signed main() { fast(); //freopen("out.txt", "w", stdout); int n, q, W; cin >> n >> q >> W; work.resize(n+1); int m = n-1; edge.resize(m); vector<int> www(m); for(int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; adj[u].pb({v, w}); adj[v].pb({u, w}); edge[i] = {{u, v}, 0}; www[i] = w; } int root = centroid_decomposition(1, 1); pa[0][0] = pa[0][root] = 0; for(int i = 1; i < LOGM; i++) { for(int u = 0; u <= n; u++) pa[i][u] = pa[0][pa[i-1][u]]; } for(int i = 1; i <= n; i++) { ANS.insert({0, i}); help[i].insert({0, 0});//ensuring there's always two elements: itself and fake zero. } for(int u = 1; u <= n; u++) { int timer = 0; cendfs(u, 0, u, timer); } for(int i = 0; i < m; i++) upd(i, www[i]); int lst = 0; while(q--) { int d, val; cin >> d >> val; d+=lst; d%=m; val+=lst; val%=W; lst = upd(d, val); cout << lst << "\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...
#Verdict Execution timeMemoryGrader output
Fetching results...