제출 #971947

#제출 시각아이디문제언어결과실행 시간메모리
971947efedmrlrDynamic Diameter (CEOI19_diameter)C++17
7 / 100
398 ms198728 KiB
#include <bits/stdc++.h> #define lli long long int #define pb push_back #define MP make_pair #define ld long double #define REP(i, n) for(int i = 0; (i) < (n); (i)++) #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() using namespace std; void fastio() { ios_base::sync_with_stdio(false); cin.tie(NULL); } const int N = 1e5 + 5; const int INF = 1e9 + 500; const int LGN = 18; struct SegT { vector<lli> st, tag; int n; void build(int tl, int tr, int v, vector<int> &x) { if(tl == tr) { st[v] = x[tl]; return; } int tm = (tl + tr) >> 1; build(tl, tm, v << 1, x); build(tm + 1, tr, v << 1 ^ 1, x); st[v] = max(st[v << 1], st[v << 1 ^ 1]); } void reset(int nn) { n = nn; st.assign(4*(n + 3), 0); tag.assign(4*(n + 3), 0); } void push(int v) { st[v << 1] += tag[v]; st[v << 1 ^ 1] += tag[v]; tag[v << 1] += tag[v]; tag[v << 1 ^ 1] += tag[v]; tag[v] = 0; } void update(int tl, int tr, int v, int l, int r, int val) { if(tl >= l && tr <= r) { st[v] += val; tag[v] += val; return; } if(tl > r || tr < l) { return; } push(v); int tm = (tl + tr) >> 1; update(tl, tm, v << 1, l, r, val); update(tm + 1, tr, v << 1 ^ 1, l, r, val); st[v] = max(st[v << 1], st[v << 1 ^ 1]); } void update(int l, int r, int val) { update(0, n, 1, l, r, val); } lli query(int tl, int tr, int v, int l, int r) { if(tl >= l && tr <= r) { return st[v]; } if(tl > r || tr < l) { return 0; } push(v); int tm = (tl + tr) >> 1; return max(query(tl, tm, v << 1, l, r), query(tm + 1, tr, v << 1 ^ 1, l, r)); } lli query(int l, int r) { return query(0, n, 1, l, r); } }; int n = 0, q = 0, w = 0; vector<vector<array<int, 2> > > adj(N, vector<array<int, 2> >()); vector<array<int, 3> > edg; vector<int> sub(N, 0); vector<int> vis(N, 0); array<SegT, LGN> st; vector<array<int, LGN> > cent(N); vector<array<int, LGN> > tin(N), p(N), ssz(N); vector<array<int, LGN> > comp(N); vector<array<int, LGN> > edgnode(N); array<int, LGN> tim; array<vector<int>, LGN> arr; vector<set<array<int, 2>, greater<array<int, 2> > > > cand(N, set<array<int, 2>, greater<array<int, 2> > >()); vector<vector<array<int, 2> > > cent_adj(N, vector<array<int, 2> >()); set<array<int, 2>, greater<array<int, 2> > > anss; vector<int> lv(N, 0); vector<int> cent_res(N, 0); void dfssz(int node, int par) { sub[node] = 1; for(auto c : adj[node]) { if(c[0] == par || vis[c[0]]) { continue; } dfssz(c[0], node); sub[node] += sub[c[0]]; } } int get_cent(int node, int par, int tar) { for(auto c : adj[node]) { if(c[0] == par || vis[c[0]]) continue; if(sub[c[0]] * 2 > tar) { return get_cent(c[0], node, tar); } } return node; } void prec(int node, int par, int lvl, int centro) { ssz[node][lvl] = 1; tin[node][lvl] = tim[lvl]++; cent[node][lvl] = centro; for(auto &c : adj[node]) { if(c[0] == par || vis[c[0]]) continue; p[c[0]][lvl] = node; edgnode[c[1]][lvl] = c[0]; prec(c[0], node, lvl, centro); ssz[node][lvl] += ssz[c[0]][lvl]; } } void prec2(int node, int par, int lvl, int g) { comp[node][lvl] = g; for(auto c : adj[node]) { if(c[0] == par || vis[c[0]]) continue; prec2(c[0], node, lvl, g); } } void prec3(int node, int par, int lvl) { for(auto c : adj[node]) { if(c[0] == par || vis[c[0]]) continue; arr[lvl][tin[c[0]][lvl]] = arr[lvl][tin[node][lvl]] + edg[c[1]][2]; prec3(c[0], node, lvl); } } void centroid_decomp(int node, int lvl) { dfssz(node, 0); int centro = get_cent(node, 0, sub[node]); lv[centro] = lvl; p[centro][lvl] = 0; prec(centro, 0, lvl, centro); for(auto c : adj[centro]) { if(vis[c[0]]) continue; cent_adj[centro].pb({c[0], 0}); prec2(c[0], centro, lvl, c[0]); } arr[lvl][centro] = 0; prec3(centro, 0, lvl); vis[centro] = 1; for(auto c : adj[node]) { if(vis[c[0]]) continue; centroid_decomp(c[0], lvl + 1); } } void solve() { REP(i, LGN) { tim[i] = 0; arr[i].assign(N, 0); REP(j, N) edgnode[j][i] = -1; } cin >> n >> q >> w; edg.resize(n - 1); REP(i, n - 1) { cin >> edg[i][0] >> edg[i][1] >> edg[i][2]; adj[edg[i][0]].pb({edg[i][1], i}); adj[edg[i][1]].pb({edg[i][0], i}); } centroid_decomp(1, 0); REP(i, LGN) { st[i].reset(n + 1); st[i].build(0, st[i].n, 1, arr[i]); } for(int i = 1; i <= n; i++) { sort(all(cent_adj[i])); for(auto &c : cent_adj[i]) { int v = st[lv[i]].query(tin[c[0]][lv[i]], tin[c[0]][lv[i]] + ssz[c[0]][lv[i]] - 1); cand[i].insert({v, c[0]}); c[1] = v; } cand[i].insert({0, -1}); cand[i].insert({0, -2}); cent_res[i] = (*cand[i].begin())[0] + (*next(cand[i].begin()))[0]; anss.insert({cent_res[i], i}); } int last = 0; REP(z, q) { int d, e; cin >> d >> e; d = (d + last) % (n - 1); e = (e + last) % w; // cout << "d:" << d <<" e:" << e << "\n"; for(int i = 0; i < LGN; i++) { if(edgnode[d][i] == -1) continue; // cout << "level:" << i << "\n"; int node = edgnode[d][i]; int centr = cent[node][i]; int rep = comp[node][i]; auto itr = lower_bound(all(cent_adj[centr]), array<int, 2>({rep, 0})); assert(rep == (*itr)[0]); // cout << "node :" << node << " centr:" << centr << " rep:" << rep << " "; cand[centr].erase({(*itr)[1], rep}); st[i].update(tin[node][i], tin[node][i] + ssz[node][i] - 1, e - edg[d][2]); // cout << "old val: " << (*itr)[1] << " "; (*itr)[1] = st[i].query(tin[rep][i], tin[rep][i] + ssz[rep][i] - 1); // cout << "new val: " << (*itr)[1] << "\n"; cand[centr].insert({(*itr)[1], rep}); anss.erase({cent_res[centr], centr}); cent_res[centr] = (*cand[centr].begin())[0] + (*next(cand[centr].begin()))[0]; anss.insert({cent_res[centr], centr}); } edg[d][2] = e; // cout << "centro:" << (*anss.begin())[1] << " lvl:" << lv[(*anss.begin())[1]] << "\n"; last = (*anss.begin())[0]; cout << last << "\n"; } } signed main() { fastio(); 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...