(UPD: 2024-12-04 14:48 UTC) Judge is not working due to Cloudflare incident. (URL) We can do nothing about it, sorry. After the incident is resolved, we will grade all submissions.

제출 #259992

#제출 시각아이디문제언어결과실행 시간메모리
259992dooweyDynamic Diameter (CEOI19_diameter)C++14
100 / 100
4962 ms202412 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; #define fi first #define se second #define mp make_pair #define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int N = (int)1e5 + 2; ll ww[N]; vector<pii> T[N]; struct Edge{ int id; int op_l; int op_r; int el; int er; }; vector<Edge> G[N]; const int M = (int)180000; struct Node{ ll val; ll lazy; }; set<pair<ll,int>> all_di; struct Centroid{ set<pair<ll,int>> best; vector<Node> Tree; int CURN; int thi_id; void init(int n){ CURN = n; for(int i = 0 ; i <= n * 4 + 8; i ++) { Tree.push_back({0,0}); } } void push(int node, int cl, int cr){ Tree[node].val += Tree[node].lazy; if(cl != cr){ Tree[node * 2].lazy += Tree[node].lazy; Tree[node * 2 + 1].lazy += Tree[node].lazy; } Tree[node].lazy = 0; } void upd(int node, int cl, int cr, int tl, int tr, ll v){ push(node, cl, cr); if(cr < tl) return; if(cl > tr) return; if(cl >= tl && cr <= tr){ Tree[node].lazy += v; push(node, cl, cr); return; } int mid = (cl + cr) / 2; upd(node << 1, cl, mid, tl, tr, v); upd(node << 1 | 1, mid + 1, cr, tl, tr, v); Tree[node].val = max(Tree[node << 1].val, Tree[node << 1 | 1].val); } ll get(int node, int cl, int cr, int tl, int tr){ push(node, cl, cr); if(cr < tl) return 0ll; if(cl > tr) return 0ll; if(cl >= tl && cr <= tr){ return Tree[node].val; } int mid = (cl + cr) / 2; return max(get(node << 1, cl, mid, tl, tr), get(node << 1 | 1, mid + 1, cr, tl, tr)); } void check(int mode){ ll sum = 0; auto it = best.end(); for(int j = 0 ; j < 2; j ++ ){ if(it != best.begin()){ it -- ; sum += it->fi; } else{ break; } } if(mode == 1){ all_di.insert(mp(sum,thi_id)); } else{ all_di.erase(mp(sum,thi_id)); } } }; vector<Centroid>shi; int idccc = 0; bool ban[N]; int subt[N]; void dfs1(int u, int par){ subt[u]=1; for(auto x : T[u]){ if(ban[x.fi] || x.fi == par) continue; dfs1(x.fi, u); subt[u] += subt[x.fi]; } } int cc; int tin[N]; int tout[N]; int las; int sz; void dfs2(int u, int par){ tin[u] = cc++; int ni, nj; for(auto x : T[u]){ if(ban[x.fi] || x.fi == par) continue; dfs2(x.fi, u); } tout[u] = cc - 1; } void dfs3(int u, int par, int l1, int r1){ int ni, nj; for(auto x : T[u]){ if(ban[x.fi] || x.fi == par) continue; ni = l1, nj = r1; if(ni == -1) ni = tin[x.fi], nj = tout[x.fi]; dfs3(x.fi, u, ni, nj); shi[las].upd(1, 0, sz - 1, tin[x.fi], tout[x.fi], +ww[x.se]); G[x.se].push_back({las, tin[x.fi], tout[x.fi], ni, nj}); if(par == -1){ shi[las].best.insert(mp(shi[las].get(1, 0, sz - 1, tin[x.fi], tout[x.fi]), ni)); } } } Centroid def; void decomp(int node){ dfs1(node, -1); int pr = -1; bool ok = true; sz = subt[node]; if(sz == 1) return; while(ok){ ok = false; for(auto x : T[node]){ if(ban[x.fi] || x.fi == pr) continue; if(subt[x.fi] > sz/2){ pr = node; node = x.fi; ok = true; break; } } } shi.push_back(def); shi[idccc].init(sz); shi[idccc].thi_id = idccc; las=idccc; idccc ++ ; cc = 0; dfs2(node, -1); dfs3(node, -1, -1, -1); shi[las].check(1); ban[node]=true; for(auto p : T[node]){ if(ban[p.fi]) continue; decomp(p.fi); } } int main(){ fastIO; ll lim; int n, q; cin >> n >> q >> lim; int u, v; for(int i = 0 ; i < n - 1; i ++ ){ cin >> u >> v >> ww[i]; T[u].push_back(mp(v, i)); T[v].push_back(mp(u, i)); } decomp(1); ll lasres = 0; ll id; ll new_w; for(int tt = 0; tt < q; tt ++ ){ cin >> id >> new_w; id += lasres; new_w += lasres; id %= (n - 1); new_w %= lim; lasres = 0; for(auto y : G[id]){ shi[y.id].check(0); shi[y.id].best.erase(mp(shi[y.id].get(1, 0, shi[y.id].CURN - 1, y.el, y.er), y.el)); shi[y.id].upd(1, 0, shi[y.id].CURN - 1, y.op_l, y.op_r, new_w - ww[id]); shi[y.id].best.insert(mp(shi[y.id].get(1, 0, shi[y.id].CURN - 1, y.el, y.er), y.el)); shi[y.id].check(1); } ww[id] = new_w; auto gt = all_di.end(); gt -- ; lasres = gt->fi; cout << lasres << "\n"; } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

diameter.cpp: In function 'void dfs2(int, int)':
diameter.cpp:126:9: warning: unused variable 'ni' [-Wunused-variable]
     int ni, nj;
         ^~
diameter.cpp:126:13: warning: unused variable 'nj' [-Wunused-variable]
     int ni, nj;
             ^~
#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...