Submission #855169

#TimeUsernameProblemLanguageResultExecution timeMemory
855169mbfibatDynamic Diameter (CEOI19_diameter)C++17
31 / 100
5061 ms373696 KiB
#include <bits/stdc++.h> using namespace std; #define int long long typedef pair<int, int> ii; const int N = 1e5 + 11; vector<ii> adj[N]; bool is_c[N]; int totChild = 0; int nChild[N]; int parCentroid[N]; void cal_child(int u, int p = 0) { nChild[u] = 1; for (auto [v, w] : adj[u]) if (!is_c[v] && v != p) { cal_child(v, u); nChild[u] += nChild[v]; } } int find_c(int u, int p = 0) { for (auto [v, w] : adj[u]) if (v != p && !is_c[v] && nChild[v] > totChild / 2) return find_c(v, u); return u; } // -------------------------------------------- unordered_map<int, int> dist; struct Node { int val = 0, lazy = 0; Node* l = nullptr, *r = nullptr; Node(){} }; // each centroid root will have a segtree Node* Seg[N]; void build(Node *cur, int l, int r) { if (l == r) { cur -> val = dist[l]; return; } cur -> l = new Node(); cur -> r = new Node(); int mi = (l + r) / 2; build(cur -> l, l, mi); build(cur -> r, mi + 1, r); cur -> val = max(cur -> l -> val, cur -> r -> val); } void diffuse(Node *cur, int l, int r) { if (cur -> lazy) { cur -> val += cur -> lazy; if (l != r) { cur -> l -> lazy += cur -> lazy; cur -> r -> lazy += cur -> lazy; } cur -> lazy = 0; } } void upd(Node *cur, int l, int r, int L, int R, int val) { diffuse(cur, l, r); if (r < L || R < l) return; if (L <= l && r <= R) { cur -> lazy += val; diffuse(cur, l, r); return; } int mi = (l + r) / 2; upd(cur -> l, l, mi, L, R, val); upd(cur -> r, mi + 1, r, L, R, val); cur -> val = max(cur -> l -> val, cur -> r -> val); } int query(Node *cur, int l, int r, int L, int R) { diffuse(cur, l, r); if (r < L || R < l) return 0; if (L <= l && r <= R) return cur -> val; int mi = (l + r) / 2; int val_l = query(cur -> l, l, mi, L, R); int val_r = query(cur -> r, mi + 1, r, L, R); return max(val_l, val_r); } int cur_root; unordered_map<int, int> top; map<ii, int> st, ed; multiset<int> val_ms[N]; vector<ii> val_ord[N]; void dfs(int u, int d = 0, int p = 0) { st[ii(cur_root, u)] = ++top[cur_root]; dist[top[cur_root]] = d; for (auto [v, w] : adj[u]) { if (is_c[v] || v == p) continue; dfs(v, d + w, u); } ed[ii(cur_root, u)] = top[cur_root]; } // get max of all paths throught u int sol[N]; multiset<int> ans; void prep(int root) { // for each centroid root, create a segment tree, using pointers to create this egment tree // store a multiset for each edge from root // using st[u] and ed[u] to get the range and know, when updating a subtree, we know what edge from root does that subtree belong // 1. create segtree: get all nodes that are !is_c[u] cur_root = root; Seg[root] = new Node(); dist[root] = 0; dfs(root); build(Seg[root], 1, top[root]); // 2. store multiset for each edge for (auto [v, w] : adj[root]) { if (is_c[v]) continue; int l = st[ii(root, v)], r = ed[ii(root, v)]; int val = query(Seg[root], 1, top[root], l, r); val_ms[root].insert(val); val_ord[root].emplace_back(l, val); } sort(val_ord[root].begin(), val_ord[root].end()); // offset for easier handling val_ms[root].insert(0); val_ms[root].insert(0); val_ord[root].emplace_back(top[root] + 1, 0); auto it = val_ms[root].rbegin(); int v1 = *it; ++it; int v2 = *it; sol[root] = v1 + v2; ans.insert(sol[root]); } // -------------------------------------------- void centroid_decompose(int u, int p = 0) { cal_child(u); totChild = nChild[u]; int c = find_c(u); parCentroid[c] = p; prep(c); is_c[c] = true; for (auto [v, w] : adj[c]) if (!is_c[v]) centroid_decompose(v, c); } void upd_edge(int root, int u1, int u2, int inc) { int u = ((st[ii(root, u1)] > st[ii(root, u2)]) ? u1 : u2); upd(Seg[root], 1, top[root], st[ii(root, u)], ed[ii(root, u)], inc); int p = upper_bound(val_ord[root].begin(), val_ord[root].end(), ii(st[ii(root, u)], 2e18)) - val_ord[root].begin() - 1; int l = val_ord[root][p].first, r = val_ord[root][p + 1].first - 1; int old_val = val_ord[root][p].second; int new_val = query(Seg[root], 1, top[root], l, r); val_ms[root].erase(val_ms[root].find(old_val)); val_ms[root].insert(new_val); val_ord[root][p].second = new_val; auto it = val_ms[root].rbegin(); int v1 = *it; ++it; int v2 = *it; ans.erase(ans.find(sol[root])); sol[root] = v1 + v2; ans.insert(sol[root]); if (parCentroid[root]) upd_edge(parCentroid[root], u1, u2, inc); } int32_t main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, q, w; cin >> n >> q >> w; vector<int> W(n); vector<ii> edges; for (int i = 0; i < n - 1; i++) { int u, v, c; cin >> u >> v >> c; W[i] = c; edges.emplace_back(u, v); adj[u].emplace_back(v, c); adj[v].emplace_back(u, c); } centroid_decompose(1); int last = 0; while (q--) { int d, e; cin >> d >> e; d = (d + last) % (n - 1); e = (e + last) % w; int dif = e - W[d]; W[d] = e; auto [u, v] = edges[d]; if (top[u] < top[v]) swap(u, v); upd_edge(u, u, v, dif); last = *ans.rbegin(); cout << last << '\n'; } }
#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...