Submission #1203085

#TimeUsernameProblemLanguageResultExecution timeMemory
1203085thinknoexitDynamic Diameter (CEOI19_diameter)C++20
100 / 100
202 ms31712 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; const int N = 100100; int n; int nds[N]; // map edges to node ll a[N]; vector<int> adj[N]; vector<pair<pair<int, int>, ll>> adj2[N]; enum Type { Compress, Vertex, AddVertex, AddEdge, Rake }; struct StaticTopTree { int l[4 * N], r[4 * N], p[4 * N], root, idx; Type t[4 * N]; int dfs(int v) { int sz = 1, big = 0; for (auto& x : adj[v]) { int s = dfs(x); sz += s; if (big < s) big = s, swap(x, adj[v][0]); } return sz; } int add(int v, int lc, int rc, Type type) { if (v == -1) v = ++idx; p[v] = -1, l[v] = lc, r[v] = rc, t[v] = type; if (lc != -1) p[lc] = v; if (rc != -1) p[rc] = v; return v; } pair<int, int> merge(vector<pair<int, int>>& path, Type type) { if ((int)path.size() == 1) return path[0]; int sz = 0; for (auto& [_, s] : path) sz += s; vector<pair<int, int>> pl, pr; for (auto& [x, s] : path) { (s < sz ? pl : pr).push_back({ x, s }), sz -= 2 * s; } auto [i, si] = merge(pl, type); auto [j, sj] = merge(pr, type); return { add(-1, i, j, type), si + sj }; } pair<int, int> rake(int i) { vector<pair<int, int>> path; for (int j = 1;j < (int)adj[i].size();j++) { path.push_back(add_edge(adj[i][j])); } return path.empty() ? make_pair(-1, 0) : merge(path, Type::Rake); } pair<int, int> compress(int i) { vector<pair<int, int>> path{ add_vertex(i) }; while (!adj[i].empty()) path.push_back(add_vertex(i = adj[i][0])); return merge(path, Type::Compress); } pair<int, int> add_vertex(int i) { auto [j, s] = rake(i); return { add(i, j, -1, j == -1 ? Type::Vertex : Type::AddVertex), s + 1 }; } pair<int, int> add_edge(int i) { auto [j, s] = compress(i); return { add(-1, j, -1, Type::AddEdge), s }; } void build() { idx = n; dfs(1); root = compress(1).first; } } stt; void dfsd(int v, int p = -1) { for (auto& x : adj2[v]) { if (x.first.second == p) continue; nds[x.first.first] = x.first.second; a[x.first.second] = x.second; adj[v].push_back(x.first.second); dfsd(x.first.second, v); } } struct Point { ll mx, mx1, mx2; } point[4 * N]; struct Path { ll mx, l, pref, mxp; } path[4 * N]; Path vertex(int i) { return { 0ll, a[i], a[i], a[i] }; } Path add_vertex(Point d, int i) { return { max(d.mx, d.mx1 + d.mx2), a[i], a[i] + d.mx1, d.mx1 }; } Path compress(Path p, Path c) { return{ max({p.mx, c.mx, p.mxp + c.pref}), p.l + c.l, max(c.pref + p.l, p.pref), max(c.mxp, p.mxp + c.l) }; } Point add_edge(Path d) { return { d.mx, d.pref, 0ll }; } Point rake(Point l, Point r) { Point res = { max(l.mx, r.mx), l.mx1, l.mx2 }; res.mx2 = max(res.mx2, r.mx1); if (res.mx1 < res.mx2) swap(res.mx1, res.mx2); res.mx2 = max(res.mx2, r.mx2); if (res.mx1 < res.mx2) swap(res.mx1, res.mx2); return res; } void update(int v) { if (stt.t[v] == Type::Vertex) path[v] = vertex(v); else if (stt.t[v] == Type::AddVertex) path[v] = add_vertex(point[stt.l[v]], v); else if (stt.t[v] == Type::Compress) path[v] = compress(path[stt.l[v]], path[stt.r[v]]); else if (stt.t[v] == Type::AddEdge) point[v] = add_edge(path[stt.l[v]]); else point[v] = rake(point[stt.l[v]], point[stt.r[v]]); } void dfs(int v) { if (stt.l[v] != -1) dfs(stt.l[v]); if (stt.r[v] != -1) dfs(stt.r[v]); update(v); } int main() { cin.tie(nullptr)->sync_with_stdio(false); int q; ll mw; cin >> n >> q >> mw; for (int i = 0;i < n - 1;i++) { int u, v; ll w; cin >> u >> v >> w; adj2[u].push_back({ {i, v}, w }); adj2[v].push_back({ {i, u}, w }); } dfsd(1); stt.build(); dfs(stt.root); ll last = 0; while (q--) { int e; ll w; cin >> e >> w; e = (e + last) % (n - 1); int v = nds[e]; a[v] = (w + last) % mw; while (v != -1) update(v), v = stt.p[v]; cout << (last = path[stt.root].mx) << '\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...