제출 #960476

#제출 시각아이디문제언어결과실행 시간메모리
960476starchanDynamic Diameter (CEOI19_diameter)C++17
0 / 100
2331 ms168152 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 build(const vector<int> &a, int id, int l, int r) { int m = (l+r)/2; if(l==r) { tree[id] = a[m]; return; } build(a, 2*id, l, m); build(a, 2*id+1, m+1, r); 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[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[X] = root; } ctout[root] = centimer; return root; } int cendfs(int u, int p, int root, int &timer, vector<int> &ref, int VALUE) { int OPT = 0; ref.pb(VALUE); 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 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; int WWW = cendfs(v, u, root, timer, ref, VALUE+w)+w; if(u == root) help[root].insert({WWW, v}); OPT = max(OPT, WWW); } tout[centh[u]-centh[root]][u] = timer; return OPT; } 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[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}, w}; } int root = centroid_decomposition(1, 1); for(int i = 1; i <= n; i++) { ANS.insert({0, i}); help[i].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; vector<int> ref; ref.pb(0); cendfs(u, 0, u, timer, ref, 0); work[u].build(ref, 1, 1, sz[u]); } 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; }

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

diameter.cpp: In function 'int main()':
diameter.cpp:196:6: warning: unused variable 'root' [-Wunused-variable]
  196 |  int root = centroid_decomposition(1, 1);
      |      ^~~~
diameter.cpp:182:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  182 |  freopen("out.txt", "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#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...