제출 #1067462

#제출 시각아이디문제언어결과실행 시간메모리
1067462TVSownDynamic Diameter (CEOI19_diameter)C++17
100 / 100
202 ms55380 KiB
///*** Sown_Vipro ***/// /// ->TUYEN QUOC GIA<- /// #include<bits/stdc++.h> using namespace std; #pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") #pragma GCC target("popcnt") #define F first #define S second #define pb push_back #define pi pair<int, int> #define pii pair<int, pair<int, int> > #define all(a) a.begin(), a.end() #define FOR(i, a, b) for(int i = a; i <= b; ++i) #define REP(i, a, b) for(int i = a; i >= b; --i) #define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin); #define out(name) if(fopen(name, "w")) freopen(name, "w", stdout); #define szz(s) int(s.size()) #define int long long const int N = 2e5 + 5, MAX = 1e6, MOD = 1e9 + 7; const long long oo = 1e18 + 5; int n, q, m, TIME; long long W, lz[4 * N], res, d[N]; int in[N], out[N], ver[N], h[N]; vector<pi> e[N]; struct ed{ int u, v; long long w; } edge[N]; void euler(int u, int p){ in[u] = ++m; out[u] = m; ver[m] = u; for(auto [v, w] : e[u]){ if(v == p) continue; h[v] = h[u] + 1; d[v] = d[u] + w; euler(v, u); } if(p != 0){ out[p] = ++m; ver[m] = p; } } struct node{ long long du = oo, dv = -oo, duw = -oo, dwv = -oo, duwv = 0; } st[4 * N]; void down(int id){ st[2 * id].du += lz[id]; st[2 * id].dv += lz[id]; st[2 * id].duw -= lz[id]; st[2 * id].dwv -= lz[id]; lz[2 * id] += lz[id]; st[2 * id + 1].du += lz[id]; st[2 * id + 1].dv += lz[id]; st[2 * id + 1].duw -= lz[id]; st[2 * id + 1].dwv -= lz[id]; lz[2 * id + 1] += lz[id]; lz[id] = 0; } long long minimize(const long long &A, const long long &B){ if(A < B) return A; return B; } long long maximize(const long long &A, const long long &B){ if(A > B) return A; return B; } node Merge(const node &A, const node &B){ node res; res.du = minimize(A.du, B.du); res.dv = maximize(A.dv, B.dv); res.duw = maximize(A.duw, B.duw); res.duw = maximize(res.duw, A.dv - 2 * B.du); res.dwv = maximize(A.dwv, B.dwv); res.dwv = maximize(res.dwv, B.dv - 2 * A.du); res.duwv = maximize(A.duwv, B.duwv); res.duwv = maximize(res.duwv, A.duw + B.dv); res.duwv = maximize(res.duwv, A.dv + B.dwv); return res; } void build(int id, int l, int r){ if(l == r){ st[id].du = st[id].dv = d[ver[l]]; st[id].duw = st[id].dwv = -d[ver[l]]; return; } int m = (l + r) / 2; build(2 * id, l, m); build(2 * id + 1, m + 1, r); st[id] = Merge(st[2 * id], st[2 * id + 1]); } void update(int id, int l, int r, int u, int v, int x){ if(l > v || r < u) return; if(u <= l && r <= v){ st[id].du += x; st[id].dv += x; st[id].duw -= x; st[id].dwv -= x; lz[id] += x; return; } down(id); int m = (l + r) / 2; update(2 * id, l, m, u, v, x); update(2 * id + 1, m + 1, r, u, v, x); st[id] = Merge(st[2 * id], st[2 * id + 1]); } void solve(){ cin >> n >> q >> W; FOR(i, 1, n - 1){ int u, v, w; cin >> u >> v >> w; e[u].pb({v, w}); e[v].pb({u, w}); edge[i] = {u, v, w}; } euler(1, 0); build(1, 1, m); while(q--){ int d; long long e; cin >> d >> e; d = (d + res) % (n - 1) + 1; e = (e + res) % W; int u = edge[d].u, v = edge[d].v, w = edge[d].w; if(h[u] > h[v]) swap(u, v); update(1, 1, m, in[v], out[v], e - w); res = st[1].duwv; cout << res << "\n"; edge[d].w = e; // break; } } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); // inp("in.txt"); // out("out.txt"); int t = 1; // cin >> t; while(t--){ solve(); } }
#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...