제출 #239176

#제출 시각아이디문제언어결과실행 시간메모리
239176crackersamdjamDynamic Diameter (CEOI19_diameter)C++14
31 / 100
5070 ms150232 KiB
#pragma GCC optimize("O3") #pragma GCC target("sse4") #include <bits/stdc++.h> #define all(x) (x).begin(), (x).end() #define gc getchar_unlocked() #define pc(x) putchar_unlocked(x) template<typename T> void scan(T &x){x = 0;bool _=0;T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;} template<typename T> void printn(T n){bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=n%10+48;n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);} template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);} template<typename T> void print(T n){printn(n);pc(10);} template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);} typedef long long ll; typedef long long T; constexpr int MM = 1e5+2, LOG = 17; int n, q, tot, sz[MM], a[MM], b[MM], dep[LOG][MM], in[LOG][MM], out[LOG][MM], t[LOG], centid[LOG][MM], parid[LOG][MM]; ll maxw, c[MM]; std::vector<std::pair<int, ll>> adj[MM]; bool vis[MM]; //all best, ch set for each node as centroid struct Combine { using Data = ll; using Lazy = ll; const Data qdef = 0; const Lazy ldef = 0; Data merge(const Data &l, const Data &r) const { return std::max(l, r); } Data applyLazy(const Data &l, const Lazy &r) const { return l + r; } Lazy getSegmentVal(const Lazy &v, int k) const { return v; } Lazy mergeLazy(const Lazy &l, const Lazy &r) const { return l + r; } }; struct Combine2 { using Data = std::pair<ll, ll>; using Lazy = ll; const Data qdef = {0, 0}; const Lazy ldef = 0; Data merge(const Data &l, const Data &r) const { std::vector<ll> v = {l.first, l.second, r.first, r.second}; sort(all(v), std::greater<ll>()); return {v[0], v[1]}; } Data applyLazy(const Data &l, const Lazy &r) const { return {r, 0}; //root node } Lazy getSegmentVal(const Lazy &v, int k) const { return v; } Lazy mergeLazy(const Lazy &l, const Lazy &r) const { return r; } }; // Time Complexity: // constructor: O(N) // update, query: O(log N) // Memory Complexity: O(N) // Tested: // https://dmoj.ca/problem/dmopc17c4p6 // https://dmoj.ca/problem/dmopc18c5p5 // https://dmoj.ca/problem/dmopc18c6p5 // https://dmoj.ca/problem/lazy // https://mcpt.ca/problem/seq3 template <class Combine> struct SegmentTreeLazyBottomUp { using Data = typename Combine::Data; using Lazy = typename Combine::Lazy; Combine C; int N, lgN; std::vector<Data> TR; std::vector<Lazy> LZ; void apply(int i, const Lazy &v, int k) { TR[i] = C.applyLazy(TR[i], C.getSegmentVal(v, k)); if (i < N) LZ[i] = C.mergeLazy(LZ[i], v); } void pushup(int i) { for (int k = 2; i /= 2; k *= 2) { TR[i] = C.merge(TR[i * 2], TR[i * 2 + 1]); if (LZ[i] != C.ldef) TR[i] = C.applyLazy(TR[i], C.getSegmentVal(LZ[i], k)); } } void propagate(int i) { int h = lgN + 1, k = 1 << lgN, ii = i >> h; for (; h > 0; ii = i >> --h, k /= 2){ // std::cout<<LZ[ii]<<std::endl; // std::cout<<C.ldef<<std::endl; if (LZ[ii] != C.ldef) { apply(ii * 2, LZ[ii], k); apply(ii * 2 + 1, LZ[ii], k); LZ[ii] = C.ldef; } } } void init(int n0, const Data vdef) { N = n0; lgN = std::__lg(N); TR = std::vector<Data>(N * 2, C.qdef); LZ = std::vector<Lazy>(N, C.ldef); fill(TR.begin() + N, TR.end(), vdef); for (int i = N - 1; i > 0; i--) TR[i] = C.merge(TR[i * 2], TR[i * 2 + 1]); } void update(int l, int r, const Lazy &v) { int l0 = l += N, r0 = r += N, k = 1; propagate(l); propagate(r); for (; l <= r; l /= 2, r /= 2, k *= 2) { if (l & 1) apply(l++, v, k); if (!(r & 1)) apply(r--, v, k); } pushup(l0); pushup(r0); } Data query(int l, int r) { propagate(l += N); propagate(r += N); Data ql = C.qdef, qr = C.qdef; for (; l <= r; l /= 2, r /= 2) { if (l & 1) ql = C.merge(ql, TR[l++]); if (!(r & 1)) qr = C.merge(TR[r--], qr); } return C.merge(ql, qr); } }; SegmentTreeLazyBottomUp<Combine> ST[LOG]; SegmentTreeLazyBottomUp<Combine2> BEST, CH[LOG]; int getsz(int cur, int pre){ sz[cur] = 1; for(auto e: adj[cur]){ int u = e.first; if(u != pre && !vis[u]) sz[cur] += getsz(u, cur); } return sz[cur]; } int findcent(int cur, int pre){ for(auto e: adj[cur]){ int u = e.first; if(!vis[u] && u != pre && sz[u]*2 > tot) return findcent(u, cur); } return cur; } void dfs1(int cur, int pre, int lvl, int cent, ll w){ in[lvl][cur] = ++t[lvl]; dep[lvl][cur] = dep[lvl][pre]+1; centid[lvl][cur] = cent; parid[lvl][cur] = pre == cent ? cur : parid[lvl][pre]; for(auto u: adj[cur]){ if(u.first == pre || vis[u.first]) continue; dfs1(u.first, cur, lvl, cent, u.second); } out[lvl][cur] = t[lvl]; ST[lvl].update(in[lvl][cur], out[lvl][cur], w); } void go(int root, int lvl){ getsz(root, -1); tot = sz[root]; if(tot == 1) return; int cent = findcent(root, -1); vis[cent] = 1; dfs1(cent, 0, lvl, cent, 0); for(auto u: adj[cent]){ if(vis[u.first]) continue; int st = in[lvl][u.first], ed = out[lvl][u.first]; ll v = ST[lvl].query(st, ed); CH[lvl].update(in[lvl][u.first], in[lvl][u.first], v); // print(lvl, u.first, v); // ch[cent].insert(v); } // while(ch[cent].size() < 2) // ch[cent].insert(0); // auto ptr = ch[cent].begin(); // best.insert(*ptr + *++ptr); auto tmp = CH[lvl].query(in[lvl][cent], out[lvl][cent]); // print(in[lvl][cent], out[lvl][cent]); // print(tmp.first, tmp.second); BEST.update(cent, cent, tmp.first+tmp.second); for(auto u: adj[cent]){ if(!vis[u.first]) go(u.first, lvl+1); } } int main(){ scan(n, q, maxw); for(int i = 0; i < n-1; i++){ scan(a[i], b[i], c[i]); adj[a[i]].emplace_back(b[i], c[i]); adj[b[i]].emplace_back(a[i], c[i]); } for(int i = 0; i < LOG; i++){ ST[i].init(MM, 0); CH[i].init(MM, {0, 0}); } BEST.init(MM, {0, 0}); go(1, 0); ll d, e, last = 0; while(q--){ scan(d, e); d = (d+last)%(n-1); e = (e+last)%maxw; int aa = a[d], bb = b[d]; ll dif = e-c[d]; c[d] = e; for(int i = 0; i < LOG; i++){ int cent = centid[i][aa]; if(cent and cent == centid[i][bb]){ if(dep[i][aa] < dep[i][bb]) std::swap(aa, bb); //aa is deeper, update it // auto ptr = ch[cent].begin(); // best.erase(best.lower_bound(*ptr + *++ptr)); int par = parid[i][aa]; // ch[cent].erase(ch[cent].lower_bound(ST[i].query(in[i][par], out[i][par]))); ST[i].update(in[i][aa], out[i][aa], dif); // ch[cent].insert(ST[i].query(in[i][par], out[i][par]));] ll v = ST[i].query(in[i][par], out[i][par]); CH[i].update(in[i][par], in[i][par], v); //okay... auto tmp = CH[i].query(in[i][cent], out[i][cent]); BEST.update(cent, cent, tmp.first+tmp.second); // print(tmp.first, tmp.second); // ptr = ch[cent].begin(); // best.insert(*ptr + *++ptr); } } // print(last = *best.begin()); print(last = BEST.query(1, n).first); } } /* * ett each centroid * when update edge, loop through LOG levels * if for any lvl, there is a point where centid[lvl][a] == centid[lvl][b] != 0, then update the one with higher depth * then for its centid, remove old ans from multiset and insert new one * */
#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...