Submission #532666

#TimeUsernameProblemLanguageResultExecution timeMemory
532666mat50013Dynamic Diameter (CEOI19_diameter)C++11
42 / 100
5062 ms134120 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int NMAX(100005); vector<pair<int, ll> > G[NMAX]; vector<int> frati[NMAX]; map<pair<int, int>, vector<pair<int, int> > > mp; bool dead[NMAX], mark[NMAX], viz[NMAX]; int pas, dim, sz[NMAX], tip[NMAX], cnt, baza, mov, id[NMAX]; ll dist[NMAX], maxx[NMAX]; struct SEGTREE { vector<ll> Arb, lazy; vector<int> in, out; int cati, ma; inline void init(int n) { cati = n; int put = 1; while(put <= n) put <<= 1; put <<= 1; ma = put; Arb.resize(put), in.resize(put), out.resize(put), lazy.resize(put); } inline void build(int nod, int st, int dr) { if(st == dr) { Arb[nod] = dist[st]; return; } int mij = (st + dr) / 2; build(2 * nod, st, mij); build(2 * nod + 1, mij + 1, dr); Arb[nod] = max(Arb[2 * nod], Arb[2 * nod + 1]); } inline void push(int nod){ if(lazy[nod]){ if(2 * nod <= ma) Arb[2 * nod] += lazy[nod], lazy[2 * nod] += lazy[nod]; if(2 * nod + 1 <= ma) Arb[2 * nod + 1] += lazy[nod], lazy[2 * nod + 1] += lazy[nod]; lazy[nod] = 0; } } inline void update(int nod, int st, int dr, int a, int b, ll val){ if(a <= st && dr <= b){ lazy[nod] += val; Arb[nod] += val; push(nod); return; } push(nod); int mij = (st + dr) / 2; if(a <= mij) update(2 * nod, st, mij, a, b, val); if(b > mij) update(2 * nod + 1, mij + 1, dr, a, b, val); Arb[nod] = max(Arb[2 * nod], Arb[2 * nod + 1]); } inline ll query(int nod, int st, int dr, int a, int b){ if(a <= st && dr <= b) return Arb[nod]; push(nod); int mij = (st + dr) / 2; ll rez1 = 0, rez2 = 0; if(a <= mij) rez1 = query(2 * nod, st, mij, a, b); if(b > mij) rez2 = query(2 * nod + 1, mij + 1, dr, a, b); return max(rez1, rez2); } } interv[NMAX]; inline int getC(int nod) { viz[nod] = 1; sz[nod] = 1; int maxx = 0; for(auto it: G[nod]) if(!viz[it.first] && mark[it.first]) { int c = getC(it.first); if(c != -1) return c; sz[nod] += sz[it.first]; maxx = max(maxx, sz[it.first]); } maxx = max(maxx, dim - sz[nod]); if(maxx <= dim / 2) return nod; return -1; } inline void DFS(int nod) { viz[nod] = 1; tip[nod] = cnt; for(auto it: G[nod]) if(!viz[it.first] && mark[it.first]) DFS(it.first); } inline void buildTree(int nod, int tata = -1) { interv[baza].in[id[nod]] = ++mov; for(auto it: G[nod]) if(tata != it.first && mark[it.first]) { mp[ {min(it.first, nod), max(it.first, nod)}].push_back({id[it.first], baza}); dist[mov + 1] = dist[interv[baza].in[id[nod]]] + it.second; buildTree(it.first, nod); } interv[baza].out[id[nod]] = mov; } inline void centroidDecomp(vector<int> nodes) { if(nodes.size() == 1) return; int mr = 0; for(auto it: nodes) mark[it] = 1, sz[it] = tip[it] = 0, viz[it] = 0, id[it] = ++mr; dim = nodes.size(); int cen = getC(nodes[0]); baza = cen; mov = dist[1] = 0; interv[baza].init(nodes.size()); buildTree(cen); interv[baza].build(1, 1, nodes.size()); for(auto it: nodes) viz[it] = 0; viz[cen] = 1; cnt = 0; for(auto it: G[cen]) if(!viz[it.first] && mark[it.first]) { frati[cen].push_back(id[it.first]); ++cnt; DFS(it.first); } vector<vector<int> > nex(cnt + 1); for(auto it: nodes) nex[tip[it]].push_back(it); for(auto it: nodes) mark[it] = 0, sz[it] = tip[it] = 0, viz[it] = 0; int nn = cnt; for(int i = 1; i <= nn; ++i) centroidDecomp(nex[i]); } int main() { ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); int n, q; ll w; cin >> n >> q >> w; vector<tuple<int, int, ll> > Muchie; for(int i = 1; i < n; ++i) { int a, b; ll c; cin >> a >> b >> c; Muchie.push_back(make_tuple(min(a, b), max(a, b), c)); G[a].push_back({b, c}); G[b].push_back({a, c}); } vector<int> noduri; for(int i = 1; i <= n; ++i) noduri.push_back(i); centroidDecomp(noduri); auto calc = [](int i) { vector<ll> vec; for(auto it: frati[i]) { ll val = interv[i].query(1, 1, interv[i].cati, interv[i].in[it], interv[i].out[it]); vec.push_back(val); } sort(vec.begin(), vec.end(), greater<ll>()); ll maxxx = 0; if(vec.size() > 1) maxxx = vec[0] + vec[1]; else maxxx = vec[0]; return maxxx; }; multiset<ll> s; for(int i = 1; i <= n; ++i) if(frati[i].size()) maxx[i] = calc(i), s.insert(-maxx[i]); ll last = 0; for(int i = 1; i <= q; ++i) { int d; ll e; cin >> d >> e; d = (d + last) % (n - 1); e = (e + last) % w; int x, y; ll c; tie(x, y, c) = Muchie[d]; for(auto it: mp[ {x, y}]){ interv[it.second].update(1, 1, interv[it.second].cati, interv[it.second].in[it.first], interv[it.second].out[it.first], e - c); s.erase(s.find(-maxx[it.second])); maxx[it.second] = calc(it.second); s.insert(-maxx[it.second]); } Muchie[d] = make_tuple(x, y, e); cout << -*s.begin() << '\n'; last = -*s.begin(); } 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...