Submission #531153

#TimeUsernameProblemLanguageResultExecution timeMemory
531153Alex_tz307Dynamic Diameter (CEOI19_diameter)C++17
100 / 100
4894 ms377832 KiB
#include <bits/stdc++.h> using namespace std; const int kN = 1e5; multiset<int64_t> diameters{0}; void maxSelf(int64_t &x, int64_t y) { if (x < y) { x = y; } } struct Centroid { int n, root, timer; vector<int> nodes, tin, tout, child, dep; vector<tuple<int, int, int64_t>> edges; vector<vector<int>> g; vector<int64_t> wt, dp, maxDist, dpLin; multiset<int64_t> paths; struct ST { int n; vector<int64_t> t, lazy, dp; void init(int N, const vector<int64_t> &aux) { n = N; int dim = 1; while (dim < n) { dim *= 2; } dim *= 2; t.resize(dim); lazy.resize(dim); dp = aux; } void build(int x, int lx, int rx) { if (lx == rx) { t[x] = dp[lx]; return; } int mid = (lx + rx) / 2; build(x * 2, lx, mid); build(x * 2 + 1, mid + 1, rx); t[x] = max(t[x * 2], t[x * 2 + 1]); } void updateNode(int x, int64_t v) { t[x] += v; lazy[x] += v; } void push(int x) { if (lazy[x] == 0) { return; } for (int i = 0; i < 2; ++i) { updateNode(x * 2 + i, lazy[x]); } lazy[x] = 0; } void update(int x, int lx, int rx, int st, int dr, int64_t v) { if (st <= lx && rx <= dr) { updateNode(x, v); return; } push(x); int mid = (lx + rx) / 2; if (st <= mid) { update(x * 2, lx, mid, st, dr, v); } if (mid < dr) { update(x * 2 + 1, mid + 1, rx, st, dr, v); } t[x] = max(t[x * 2], t[x * 2 + 1]); } void update(int st, int dr, int64_t v) { update(1, 1, n, st, dr, v); } int64_t query(int x, int lx, int rx, int st, int dr) { if (st <= lx && rx <= dr) { return t[x]; } push(x); int mid = (lx + rx) / 2; int64_t ans = 0; if (st <= mid) { maxSelf(ans, query(x * 2, lx, mid, st, dr)); } if (mid < dr) { maxSelf(ans, query(x * 2 + 1, mid + 1, rx, st, dr)); } return ans; } int64_t query(int st, int dr) { return query(1, 1, n, st, dr); } } t; void setRoot(int v) { root = v; } void addNode(int v) { nodes.emplace_back(v); } void addEdge(int u, int v, int64_t w) { edges.emplace_back(u, v, w); } int getIndex(int v) { return distance(nodes.begin(), upper_bound(nodes.begin(), nodes.end(), v)); } void dfs(int u, int par) { tin[u] = ++timer; maxDist[u] = dp[u]; for (int v : g[u]) { if (v != par) { if (par == 0) { child[v] = v; } else { child[v] = child[u]; } dep[v] = dep[u] + 1; dp[v] = dp[u] + wt[v]; dfs(v, u); maxSelf(maxDist[u], maxDist[v]); } } tout[u] = timer; } int64_t getDiameter(int dbg) { auto it = paths.end(); --it; int64_t len = *it; if ((int)paths.size() >= 2) { --it; len += *it; } /* if (dbg == 100) { cout << endl; cout << "ULTIMELE 2 SUNT " << *paths.rbegin() << ' ' << *prev(paths.rbegin()) << endl; for (auto it : paths) { cout << it << ' '; } cout << endl << endl; } if (dbg == 100) { cout << "CEVA 100 " << endl; for (auto it : paths) { cout << it << ' '; } cout << endl; } if (dbg == 100) { cout << "ADAUG " << len << endl; } */ return len; } void addDiameter(int dbg = 0) { /* if (dbg == 100) { cout << "CEVA " << endl; for (auto it : paths) { cout << it << ' '; } cout << endl; } */ diameters.emplace(getDiameter(dbg)); } void removeDiameter() { diameters.erase(diameters.find(getDiameter(1))); } /* 10 1 10000 1 9 1241 5 6 1630 10 5 1630 2 6 853 10 1 511 5 3 760 8 3 1076 4 10 1483 7 10 40 8 2051 */ /* 10 0 10000 1 9 1241 5 6 1630 10 5 1630 2 6 853 10 1 511 5 3 760 8 3 1076 4 10 1483 7 10 40 */ void build() { /// cout << "CONSTRUIESC ARBORELE CENTROIDULUI " << root << endl; /// cout << "AM " << nodes.size() << " NODURI" << endl; /// cout << endl; sort(nodes.begin(), nodes.end()); root = getIndex(root); n = nodes.size(); g.resize(n + 1); wt.resize(n + 1); for (auto it : edges) { int u, v; int64_t w; tie(u, v, w) = it; u = getIndex(u); v = getIndex(v); g[u].emplace_back(v); wt[v] = w; } timer = 0; tin.resize(n + 1); tout.resize(n + 1); dp.resize(n + 1); maxDist.resize(n + 1); child.resize(n + 1); dep.resize(n + 1); dfs(root, 0); dpLin.resize(n + 1); for (int v = 1; v <= n; ++v) { dpLin[tin[v]] = dp[v]; } t.init(n, dpLin); t.build(1, 1, n); for (int v : g[root]) { paths.emplace(maxDist[v]); } addDiameter(); } void updateEdge(int v, int64_t w) { ///cout << "CEVA" << endl; removeDiameter(); v = getIndex(v); int son = child[v]; ///cout << son << ' ' << v << endl; ///cout << wt[v] << endl; paths.erase(paths.find(t.query(tin[son], tout[son]))); t.update(tin[v], tout[v], w - wt[v]); wt[v] = w; paths.emplace(t.query(tin[son], tout[son])); addDiameter(100); } } C[1 + kN]; int sz[1 + kN]; vector<pair<int, int64_t>> g[1 + kN]; pair<int, int> edges[1 + kN]; bitset<1 + kN> vis; map<pair<int, int>, vector<int>> centroids; void findSize(int u, int par) { sz[u] = 1; for (auto it : g[u]) { int v = it.first; if (!vis[v] && v != par) { findSize(v, u); sz[u] += sz[v]; } } } int findCentroid(int u, int par, int n) { for (auto it : g[u]) { int v = it.first; if (!vis[v] && v != par && sz[v] > n / 2) { return findCentroid(v, u, n); } } return u; } void dfs(int u, int par, int centroid) { if (par) { centroids[{par, u}].emplace_back(centroid); } C[centroid].addNode(u); for (auto it : g[u]) { int v; int64_t w; tie(v, w) = it; if (!vis[v] && v != par) { C[centroid].addEdge(u, v, w); dfs(v, u, centroid); } } } void build(int u) { findSize(u, 0); if (sz[u] == 1) { return; } int c = findCentroid(u, 0, sz[u]); /// cout << "CENTROID " << c << endl; vis[c] = true; C[c].setRoot(c); dfs(c, 0, c); C[c].build(); for (auto it : g[c]) { int v = it.first; if (!vis[v]) { build(v); } } } void testCase() { int n, q; int64_t W; cin >> n >> q >> W; for (int i = 1; i < n; ++i) { int u, v; int64_t w; cin >> u >> v >> w; g[u].emplace_back(v, w); g[v].emplace_back(u, w); edges[i] = {u, v}; } build(1); int64_t last = 0; /// cout << *diameters.rbegin() << endl; for (int i = 1; i <= q; ++i) { int d; int64_t w; cin >> d >> w; d = (last + d) % (n - 1); w = (last + w) % W; d += 1; int u, v; tie(u, v) = edges[d]; for (int c : centroids[{u, v}]) { C[c].updateEdge(v, w); } for (int c : centroids[{v, u}]) { C[c].updateEdge(u, w); } last = *diameters.rbegin(); cout << last << '\n'; } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int tests = 1; for (int tc = 0; tc < tests; ++tc) { testCase(); } 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...