제출 #290022

#제출 시각아이디문제언어결과실행 시간메모리
290022ngotienhungDynamic Diameter (CEOI19_diameter)C++14
24 / 100
570 ms69496 KiB
#include <bits/stdc++.h> #define int long long #define fi first #define se second #define pb push_back using namespace std; const int maxN = 1e5 + 10; const int inf = 1e18; struct TEdge{int u, v, w;}; int n,q,w,v; int timer = 0; int vtx[maxN], tin[maxN], tout[maxN], a[maxN], d[maxN]; TEdge e[maxN]; vector<int> adj[maxN]; struct Node { int d1, d2, d12, d23, d123, tmp; void add(int t){ d1 += t; d2 += t; d12 -= t; d23 -= t; tmp += t; } void push(Node& a, Node& b){ a.add(tmp); b.add(tmp); } } st[maxN * 4]; Node operator + (Node a, Node b){ Node x; x.d1 = max(a.d1, b.d1); x.d2 = min(a.d2, b.d2); x.d12 = max(a.d12, max(b.d12, a.d1 - b.d2 * 2)); x.d23 = max({a.d23, b.d23, -2 * a.d2 + b.d1}); x.d123 = max(max(a.d123, b.d123), max(a.d12 + b.d1, a.d1 + b.d23)); x.tmp = 0; return x; } void dfs(int u){ tin[u] = timer; for(auto x : adj[u]){ if(vtx[x] != u){ if(e[x].u == u) v = e[x].v; else v = e[x].u; vtx[x] = v; d[v] = d[u] + e[x].w; a[timer++] = d[u]; dfs(v); } } a[timer++] = d[u]; tout[u] = timer; } void build(int id, int l, int r){ if(l + 1 == r){ st[id] = {a[l], a[l], -inf, -inf, 0, 0}; } else{ build(id << 1, l, (l + r) >> 1); build(id << 1 | 1, (l + r) >> 1, r); st[id] = st[id << 1] + st[id << 1 | 1]; } } void update(int id, int l, int r, int u, int v, int d){ if(u <= l && r <= v){ st[id].add(d); return; } if(r <= u || l >= v) return; st[id].push(st[id << 1], st[id << 1 | 1]); int mid = (l + r) >> 1; update(id << 1, l, mid, u, v, d); update(id << 1 | 1, mid, r, u, v, d); st[id] = st[id << 1] + st[id << 1 | 1]; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(); cout.tie(); //freopen("DD.inp", "r", stdin); cin >> n >> q >> w; for(int i = 0; i < n - 1; ++i){ cin >> e[i].u >> e[i].v >> e[i].w; adj[e[i].u].pb(i); adj[e[i].v].pb(i); } dfs(1); build(1, 0, 2 * n - 1); int last = 0; for(int i = 1; i <= q; ++i){ int x,y; cin >> x >> y; x = (x + last) % (n - 1); y = (y + last) % w; int u = vtx[x]; update(1, 0, 2 * n - 1, tin[u], tout[u], y - e[x].w); e[x].w = y; last = max(st[1].d1, st[1].d123); cout << last << endl; } }
#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...