Submission #1245176

#TimeUsernameProblemLanguageResultExecution timeMemory
1245176Mousa_AboubakerDynamic Diameter (CEOI19_diameter)C++20
31 / 100
280 ms25988 KiB
#include <bits/stdc++.h> using namespace std; template <typename T> using pqg = priority_queue<T, vector<T>, greater<T>>; struct LazySegmentTree { int n; vector<long long> seg; vector<long long> lazy; void push(int v) { lazy[v * 2] += lazy[v]; lazy[v * 2 + 1] += lazy[v]; seg[v * 2] += lazy[v]; seg[v * 2 + 1] += lazy[v]; lazy[v] = 0; } LazySegmentTree(int _n) { n = _n; seg.assign(n * 4, 0); lazy.assign(n * 4, 0); } void update(int l, int r, long long val, int tl, int tr, int v) { if (r < tl or tr < l) return; if (l <= tl and tr <= r) { seg[v] += val; lazy[v] += val; return; } push(v); int md = (tl + tr) / 2; update(l, r, val, tl, md, v * 2); update(l, r, val, md + 1, tr, v * 2 + 1); seg[v] = max(seg[v * 2], seg[v * 2 + 1]); } void update(int l, int r, long long val) { update(l, r, val, 0, n - 1, 1); } long long query(int l, int r, int tl, int tr, int v) { if (r < tl or tr < l) return 0; if (l <= tl and tr <= r) return seg[v]; push(v); int md = (tl + tr) / 2; return max(query(l, r, tl, md, v * 2), query(l, r, md + 1, tr, v * 2 + 1)); } long long query(int l, int r) { return query(l, r, 0, n - 1, 1); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; long long w; cin >> n >> q >> w; vector<tuple<int, int, long long>> edges(n); for (int i = 1; i < n; i++) { auto &[u, v, c] = edges[i]; cin >> u >> v >> c; if (u > v) swap(u, v); } vector adj(n + 1, vector<pair<int, long long>>()); for (int i = 1; i < n; i++) { auto [u, v, c] = edges[i]; adj[u].push_back({v, c}); adj[v].push_back({u, c}); } vector<int> in(n + 1), out(n + 1), par(n + 1), euler(n); vector<long long> sum(n + 1); LazySegmentTree seg(n); int timer = 0; auto dfs = [&](auto self, int u, int p, int pp) -> void { par[u] = pp; euler[timer] = u; in[u] = timer++; for (auto [v, c] : adj[u]) { if (v == p) continue; bool can = pp == -1; if (can) pp = v; self(self, v, u, pp); if (can) pp = -1; } out[u] = timer; }; dfs(dfs, 1, -1, -1); for (int i = 1; i < n; i++) { auto &[u, v, c] = edges[i]; if (in[u] > in[v]) swap(u, v); seg.update(in[v], out[v] - 1, c); } multiset<long long> st; st.insert(0); for (auto [v, c] : adj[1]) { st.insert(seg.query(in[v], out[v] - 1)); } long long lst = 0; while (q--) { int d; long long e; cin >> d >> e; d = (d + lst) % (n - 1) + 1; e = (e + lst) % w; auto &[u, vv, c] = edges[d]; long long bef = c; c = e; st.erase(st.find(seg.query(in[par[vv]], out[par[vv]] - 1))); // for(auto [v, c]: adj[1]) // { // cout << v << ' ' << seg.query(in[v], out[v] - 1) << '\n'; // } // cout << "\n\n"; seg.update(in[vv], out[vv] - 1, c - bef); // for(auto [v, c]: adj[1]) // { // cout << v << ' ' << seg.query(in[v], out[v] - 1) << '\n'; // } st.insert(seg.query(in[par[vv]], out[par[vv]] - 1)); long long res = *prev(st.end()) + *prev(prev(st.end())); cout << res << '\n'; lst = res; } }
#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...