제출 #467647

#제출 시각아이디문제언어결과실행 시간메모리
467647ivan_tudorDynamic Diameter (CEOI19_diameter)C++17
31 / 100
5102 ms111304 KiB
#include<bits/stdc++.h> using namespace std; // consideram initial ca toate distantele sunt 0 si apoi updatam cu costul muchiilor const int N = 100005; const int LOGN = 18; // aint long long aint[N * LOGN * 4 + 5]; long long lazy[N * LOGN * 4 + 5]; void propag(int nod, int l, int r){ aint[nod] += 1LL * lazy[nod]; if(l != r){ lazy[2*nod] += lazy[nod]; lazy[2*nod + 1] += lazy[nod]; } lazy[nod] = 0; } void update(int nod, int l, int r, int ul, int ur, long long val){ propag(nod, l, r); if(ur < l || r < ul) return; if(ul <= l && r <= ur){ lazy[nod] += val; propag(nod, l, r); return; } int mid = (l + r)/2; update(2*nod, l, mid, ul, ur, val); update(2*nod + 1, mid + 1, r, ul, ur, val); aint[nod] = max(aint[2*nod], aint[2*nod + 1]); } long long query(int nod, int l, int r, int ql, int qr){ propag(nod, l, r); if(r < ql || qr < l) return 0; if(ql <= l && r <= qr) return aint[nod]; int mid = (l + r)/2; long long ls = query(2*nod, l, mid, ql, qr); long long rs = query(2*nod + 1, mid + 1, r, ql, qr); return max(ls, rs); } vector<int> gr[N]; int croot[LOGN][N]; int fson[LOGN][N]; int in[LOGN][N]; int out[LOGN][N]; bool wasC[N]; int sz[N]; void dfs_sz(int nod, int dad){ sz[nod] = 1; for(auto x:gr[nod]){ if(x!= dad && wasC[x] == false){ dfs_sz(x, nod); sz[nod] += sz[x]; } } } int find_centro(int nod, int dad, int bound){ for(auto x:gr[nod]){ if(wasC[x] == false && x!= dad && sz[x] > bound) return find_centro(x, nod, bound); } return nod; } void dfs_from_centro(int nod, int dad, int cnumber, int &id, int centro, int fs){ if(dad == centro) fs = nod; croot[cnumber][nod] = centro; fson[cnumber][nod] = fs; in[cnumber][nod] = ++id; for(auto x:gr[nod]){ if(x != dad && wasC[x] == false){ dfs_from_centro(x, nod, cnumber, id, centro, fs); } } out[cnumber][nod] = id; } multiset<long long> best[N]; multiset<long long> bsum; void centro_dec(int nod, int number, int &id){ dfs_sz(nod, 0); int sze = sz[nod]; int centro = find_centro(nod, 0, sze / 2); dfs_from_centro(centro, 0, number, id, centro, centro); for(auto x:gr[centro]){ if(wasC[x] == false){ best[centro].insert(0); } } bsum.insert(0); wasC[centro] = true; for(auto x:gr[centro]){ if(wasC[x] == false) centro_dec(x, number + 1, id); } } int L, R; long long sumbig2(multiset<long long> &s){ long long sum =0; int cnt = 0; for(auto itr = s.rbegin(); itr != s.rend() && cnt < 2; itr++, cnt++){ sum += (*itr); } return sum; } bool isdad(int number, int dad, int son){ if(in[number][dad] <= in[number][son] && out[number][son] <= out[number][dad]) return true; return false; } void update_edge(int nod, int onod, long long change){ int number = 0; for(; number < LOGN; number++){ if(croot[number][nod] == nod) break; } while(number > 0 && croot[number][nod] != croot[number][onod]) number--; for(; number >= 0; number--){ if(isdad(number, nod, onod) == true) swap(nod, onod); int centro = croot[number][nod]; int fs = fson[number][nod]; long long o_sum = sumbig2(best[centro]); bsum.erase(bsum.find(o_sum)); long long old_big = query(1, L, R, in[number][fs], out[number][fs]); best[centro].erase(best[centro].find(old_big)); update(1, L, R, in[number][nod], out[number][nod], change); long long new_big = query(1, L, R, in[number][fs], out[number][fs]); best[centro].insert(new_big); long long nsum = sumbig2(best[centro]); bsum.insert(nsum); } } struct edges{ int x, y; long long c; }; int main() { //freopen(".in","r",stdin); ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int n, q; long long w; cin>>n>>q>>w; vector<edges> es; for(int i = 0; i < n - 1; i++){ int x, y, c; cin>>x>>y>>c; es.push_back({x, y, c}); gr[x].push_back(y); gr[y].push_back(x); } centro_dec(1, 0, R); L = 1; for(int i = 0; i < n - 1; i++){ update_edge(es[i].x, es[i].y, es[i].c); } long long last = 0; for(int i = 1; i<=q; i++){ long long d, e; cin>>d>>e; d = (last + d)%(n - 1); e = (last + e)% w; long long df = e - es[d].c; update_edge(es[d].x, es[d].y, df); es[d].c = e; last = (*bsum.rbegin()); 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...