제출 #1040755

#제출 시각아이디문제언어결과실행 시간메모리
1040755antonDynamic Diameter (CEOI19_diameter)C++17
0 / 100
508 ms40320 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> int N, Q, W; const int MAX_N = 1e5; vector<unordered_map<int, int>> adj; vector<int> group; struct SegTree{ int len =1; vector<int> lazy; vector<vector<pii>> tr; SegTree(int n){ while(len<n){ len*=2; } lazy.resize(2*len); tr.resize(2*len); } void upd(int u){ vector<pii> candidats; for(auto e: tr[u*2]){ candidats.push_back(e); } for(auto e: tr[u*2+1]){ candidats.push_back(e); } sort(candidats.begin(), candidats.end()); reverse(candidats.begin(), candidats.end()); tr[u].clear(); for(auto e: candidats){ if(tr[u].size() ==2){ break; } if(tr[u].size() == 0 || tr[u].back().second != e.second){ tr[u].push_back(e); } } for(pii& e: tr[u]){ e.first += lazy[u]; } } void insert(int id,int gid, int v, int lt, int rt, int t){ if(lt==rt){ tr[t].push_back({v, gid}); } else{ int mid =(lt+rt)/2; if(id<=mid){ insert(id, gid, v, lt, mid, t*2); } else{ insert(id, gid, v, mid+1, rt, t*2+1); } upd(t); } } void add(int l, int r,int v, int lt, int rt, int t){ if(r<lt|| rt<l){ return; } else if(l<=lt && rt<= r){ lazy[t]+= v; for(pii& e: tr[t]){ e.first +=v; } } else { int mid = (lt+rt)/2; add(l, r, v, lt, mid, t*2); add(l, r, v, mid+1, rt, t*2+1); upd(t); } } int get(){ int res = tr[1][0].first; if(tr[1].size()>1){ res += tr[1][1].first; } return res; } }; pii get_furthest(int u, int a){ pii res ={0, u}; for(auto e: adj[u]){ if(e.first!=a){ pii de = get_furthest(e.first, u); de.first += e.second; if(de.first>res.first){ res = de; } } } return res; } void euler_tour(int u, int a, vector<pii>& tour_t, int &t,vector<int>& dpth, int d, vector<bool>& leaf){ int nb_c= 0; tour_t[u].first = t; dpth[u] = d; for(auto e: adj[u]){ if(e.first!=a){ nb_c++; euler_tour(e.first, u, tour_t, t, dpth, d+e.second, leaf); } } if(nb_c == 0){ leaf[u] = true; t++; } tour_t[u].second = t; } void group_dfs(int u, int a, int gid){ group[u] = gid; for(auto e: adj[u]){ if(e.first != a){ group_dfs(e.first, u, gid); } } } signed main(){ cin>>N>>Q>>W; adj.resize(N); group.resize(N); vector<pii> edges; for(int i = 0; i<N-1; i++){ int a, b, c; cin>>a>>b>>c; a--;b--; adj[a][b] = c; adj[b][a] = c; edges.push_back({a, b}); } int root =0; vector<pii> tour_t(N); vector<int> dpth(N); vector<bool> leaf(N); int tm = 0; euler_tour(root, -1, tour_t, tm, dpth, 0, leaf); int cg= 1; for(auto e: adj[root]){ group_dfs(e.first, root, cg); cg++; } SegTree tr(N); for(int i = 0; i<N; i++){ if(leaf[i]){ tr.add(tour_t[i].first, tour_t[i].second-1, dpth[i], 0, N-1, 1); tr.insert(tour_t[i].first,group[i], dpth[i], 0, N-1, 1); } } int last= 0; for(int i = 0; i<Q; i++){ int d, e; cin>>d>>e; d = (d+last)%(N-1); e = (e +last)%W; int a = edges[d].first; int b= edges[d].second; if(dpth[a]<dpth[b]){ swap(a, b); } int delta = e-adj[a][b]; adj[a][b] = e; adj[b][a] =e; //cout<<a<<" delta "<<delta<<endl; tr.add(tour_t[a].first, tour_t[a].second-1,delta, 0, N-1, 1); int last = tr.get(); 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...