제출 #938733

#제출 시각아이디문제언어결과실행 시간메모리
938733a_l_i_r_e_z_aDynamic Diameter (CEOI19_diameter)C++17
100 / 100
225 ms53376 KiB
// In the name of God // Hope is last to die #include <bits/stdc++.h> using namespace std; // #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("avx2") typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define pb push_back // #define int long long #define S second #define F first #define mp make_pair #define smax(x, y) (x) = max((x), (y)) #define smin(x, y) (x) = min((x), (y)) #define all(x) (x).begin(), (x).end() const int maxn = 1e5 + 5; const int inf = 1e9 + 7; struct D{ ll ans, sum, mx, mn, ul, lv; } node[maxn * 8]; ll n, q, W, w[maxn], in[maxn], out[maxn]; vector<pll> adj[maxn]; vector<ll> vec; void dfs(int v, int p = -1){ for(auto [u, e]: adj[v]){ if(u == p) continue; in[e] = vec.size(); vec.pb(w[e]); dfs(u, v); out[e] = vec.size(); vec.pb(-w[e]); } } D merge(D l, D r){ D res; r.mx += l.sum; r.mn += l.sum; r.ul -= l.sum; r.lv -= l.sum; res.ans = max(l.ans, max(r.ans, max(l.ul + r.mx, l.mx + r.lv))); res.sum = l.sum + r.sum; res.mx = max(l.mx, r.mx); res.mn = min(l.mn, r.mn); res.ul = max(l.ul, max(r.ul, l.mx - 2 * r.mn)); res.lv = max(l.lv, max(r.lv, -l.mn * 2 + r.mx)); return res; } void settle(int id, ll x){ node[id].ans = abs(x); node[id].sum = x; node[id].mx = max(0ll, x); node[id].mn = min(0ll, x); node[id].ul = max(0ll, -2 * x); node[id].lv = max(0ll, x); } void build(int l = 0, int r = vec.size(), int id = 1){ if(l == r - 1){ settle(id, vec[l]); return; } int mid = (l + r) / 2; build(l, mid, id * 2); build(mid, r, id * 2 + 1); node[id] = merge(node[id * 2], node[id * 2 + 1]); } void upd(int p, ll x, int l = 0, int r = vec.size(), int id = 1){ if(l == r - 1){ settle(id, x); return; } int mid = (l + r) / 2; if(p < mid) upd(p, x, l, mid, id * 2); else upd(p, x, mid, r, id * 2 + 1); node[id] = merge(node[id * 2], node[id * 2 + 1]); } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> q >> W; for(int i = 0; i < n - 1; i++){ int u, v; cin >> u >> v >> w[i]; adj[u].pb(mp(v, i)); adj[v].pb(mp(u, i)); } dfs(1); build(); ll last = 0; while(q--){ ll d, e; cin >> d >> e; d = (d + last) % (n - 1); e = (e + last) % W; upd(in[d], e); upd(out[d], -e); last = node[1].ans; cout << last << '\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...