제출 #1006586

#제출 시각아이디문제언어결과실행 시간메모리
1006586ttttttttttttthDynamic Diameter (CEOI19_diameter)C++17
42 / 100
3132 ms481168 KiB
// Author: Ivan Teo // Created: Sun Jun 23 11:05:28 2024 #define TASKNAME "1192B" #include <bits/stdc++.h> using namespace std; #define fore(i, a, b) for (int i = (a); i <= (b); i++) #define int long long using vi = vector<int>; using ii = pair<int, int>; using iii = tuple<int, int, int>; #define pb emplace_back #define fi first #define se second #define sz(v) ((int)v.size()) #define all(v) v.begin() + 1, v.end() #define alll(v) v.begin(), v.end() #define db(x) cerr << "[" << #x << " = " << x << "]" #define el cerr << "\n=========================================\n" #define idl (id << 1) #define idr (id << 1 | 1) struct SegmentTree { int n; vector<ii> st; vi lz; SegmentTree() {} SegmentTree(int n): n(n), st(4 * n + 5), lz(4 * n + 5) { } inline void add(int id, int v) { st[id].fi += v; lz[id] += v; } inline void push(int id) { add(idl, lz[id]); add(idr, lz[id]); lz[id] = 0; } void build(int id, int l, int r, vi &dep) { if (l > r) return ; if (l == r) return (void)(st[id] = {dep[l], l}); int m = (l + r) >> 1; build(idl, l, m, dep); build(idr, m + 1, r, dep); st[id] = max(st[idl], st[idr]); } inline void add(int id, int l, int r, int tl, int tr, int v) { if (l > r || l > tr || r < tl) return ; if (l >= tl && r <= tr) return (void)(add(id, v)); push(id); int m = (l + r) >> 1; add(idl, l, m, tl, tr, v); add(idr, m + 1, r, tl, tr, v); st[id] = max(st[idl], st[idr]); } inline int get(int id, int l, int r, int tl, int tr) { if (l > r || l > tr || r < tl) return 0; if (l >= tl && r <= tr) return st[id].fi; push(id); int m = (l + r) >> 1; return max(get(idl, l, m, tl, tr), get(idr, m + 1, r, tl, tr)); } inline void add(int l, int r, int v) { add(1, 1, n, l, r, v); } inline int get(int l, int r) { return get(1, 1, n, l, r); } inline ii get() { return st[1]; } }; struct Tree { vector<vector<ii>> g; vi dep, branch, in, out, pw, l; SegmentTree st; int n, root, timer = 0, diam; vector<ii> s; void init(vector<iii> &e, int _root) { root = _root; for (auto &[u, v, w] : e) l.pb(u), l.pb(v); sort(alll(l)); l.erase(unique(alll(l)), l.end()); n = sz(l); g = vector<vector<ii>>(n + 1); pw = in = out = dep = branch = vi(n + 1); st = SegmentTree(n); for (auto &[u, v, w] : e) { s.pb(u, v); s.pb(v, u); u = lower_bound(alll(l), u) - l.begin() + 1; v = lower_bound(alll(l), v) - l.begin() + 1; g[u].pb(v, w); g[v].pb(u, w); } sort(alll(s)); root = lower_bound(alll(l), root) - l.begin() + 1; dfs(root, 0); st.build(1, 1, n, dep); } void dfs(int u, int p) { in[u] = ++timer; if (p == root) branch[timer] = u; else if (u != root) branch[timer] = branch[in[p]]; for (auto &[v, w] : g[u]) if (v != p) { dep[timer + 1] = dep[in[u]] + w; pw[v] = w; dfs(v, u); } out[u] = timer; get(); } void upd(int u, int v, int w) { auto it = lower_bound(alll(s), ii(u, v)); if (it == s.end() || *it != ii(u, v)) return ; u = lower_bound(alll(l), u) - l.begin() + 1; v = lower_bound(alll(l), v) - l.begin() + 1; if (in[u] > in[v]) swap(u, v); st.add(in[v], out[v], w - pw[v]); pw[v] = w; get(); } inline void get() { auto [dist, u] = st.get(); dist += max(st.get(1, in[branch[u]] - 1), st.get(out[branch[u]] + 1, n)); diam = dist; } }; signed main() { cin.tie(0)->sync_with_stdio(0); int n, q, W; cin >> n >> q >> W; vector<vector<iii>> g(n + 1); vector<ii> edge; vector<vi> group(n - 1); fore(i, 1, n - 1) { int u, v, w; cin >> u >> v >> w; g[u].pb(v, w, i - 1); g[v].pb(u, w, i - 1); edge.pb(u, v); } vi sz = vi(n + 1), del(n + 1); function<int(int, int, int)> centroid = [&](int u, int p, int n) { for (auto &[v, w, id] : g[u]) if (!del[v] && v != p) if (sz[v] * 2 > n) return centroid(v, u, n); return u; }; function<void(int, int)> dfs = [&](int u, int p) { sz[u] = 1; for (auto &[v, w, id] : g[u]) if (!del[v] && v != p) dfs(v, u), sz[u] += sz[v]; }; vector<iii> e; vector<Tree> jungle; function<void(int, int)> add = [&](int u, int p) { for (auto &[v, w, id] : g[u]) if (!del[v] && v != p) add(v, u), e.pb(u, v, w), group[id].pb(sz(jungle)); }; function<void(int)> go = [&](int u) { dfs(u, 0); int root = centroid(u, 0, sz[u]); del[root] = 1; e.clear(); add(root, 0); if (sz(e)) jungle.pb(), jungle.back().init(e, root); for (auto &[v, w, id] : g[root]) if (!del[v]) go(v); }; go(1); multiset<int> ms; int last = 0; fore(i, 0, sz(jungle) - 1) ms.insert(jungle[i].diam); while (q--) { int id, w; cin >> id >> w; id = (id + last) % (n - 1); w = (w + last) % W; int ans = 0; for (auto i : group[id]) { ms.erase(ms.find(jungle[i].diam)); jungle[i].upd(edge[id].fi, edge[id].se, w); ms.insert(jungle[i].diam); } ans = *ms.rbegin(); cout << ans << '\n'; last = ans; } 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...