제출 #835261

#제출 시각아이디문제언어결과실행 시간메모리
835261JosiaDynamic Diameter (CEOI19_diameter)C++17
49 / 100
5023 ms253212 KiB
#include <bits/stdc++.h> using namespace std; #define int int64_t struct seg { int n; vector<int> tree; vector<int> lazy; void push(int v) { tree[v*2] += lazy[v]; tree[v*2+1] += lazy[v]; lazy[v*2] += lazy[v]; lazy[v*2+1] += lazy[v]; lazy[v] = 0; } int query(int v, int rl, int rr, int ql, int qr) { if (ql > qr) { return 0; } if (ql == rl && qr == rr) return tree[v]; push(v); int rm = (rl + rr) / 2; return max(query(v*2, rl, rm, ql, min(rm, qr)), query(v*2+1, rm+1, rr, max(rm+1, ql), qr)); } void update(int v, int rl, int rr, int ql, int qr, int x) { if (ql > qr) { return; } if (ql == rl && qr == rr) { tree[v] += x; lazy[v] += x; return; } push(v); int rm = (rl + rr) / 2; update(v*2, rl, rm, ql, min(rm, qr), x); update(v*2+1, rm+1, rr, max(rm+1, ql), qr, x); tree[v] = max(tree[v*2], tree[v*2+1]); } void init(int _n, vector<int> a) { n = _n; tree.assign(n*4, 0); lazy.assign(n*4, 0); // for (int i = 0; i<n; i++) { // update(1, 0, n-1, i, i, a[i]); // } } }; vector<vector<int>> graph; array<array<int, 100005>, 20> parent; array<array<int, 100005>, 20> Size; array<array<int, 100005>, 20> whichSubtree; array<array<pair<int, int>, 100005>, 20> prepost; vector<int> centroidLevel; struct tree { int level; int currCol = 0; seg segtree; vector<int> order; vector<int> verticies; vector<int> children; int dfs(int v, int p, int forbidden) { verticies.push_back(v); prepost[level][v].first = order.size(); order.push_back(v); parent[level][v] = p; if (p!=-1) whichSubtree[level][v] = currCol; int s = 1; for (int i: graph[v]) { if (i == p || centroidLevel[i]!=-1) continue; s += dfs(i, v, forbidden); if (p==-1) { children.push_back(i); currCol++; } } Size[level][v] = s; prepost[level][v].second = order.size()-1; return s; } bool isCentroid(int v, int p, int forbidden) { int s = 1; for (int i: graph[v]) { if (i == p || centroidLevel[i]!=-1) continue; if (Size[level][i] > (int)verticies.size()/2) return 0; s += Size[level][i]; } return (int)verticies.size()-s <= (int)verticies.size()/2; } int findCentroid(int v, int p, int forbidden) { if (isCentroid(v, p, forbidden)) return v; int biggest=0; int indBiggest=-1; for (int i: graph[v]) { if (i == p || centroidLevel[i]!=-1) continue; if (Size[level][i] > biggest) { biggest = Size[level][i]; indBiggest = i; } } assert(indBiggest!=-1); return findCentroid(indBiggest, v, forbidden); } bool isParent(int p, int v) { return (parent[level][v] == p); } set<pair<int, int>> bestInChild; void updateEdge(int u, int v, int x) { // if (verticies.count(u)==0 || verticies.count(v)==0) return; if (!isParent(u, v)) swap(u, v); int child = whichSubtree[level][v]; pair<int, int> rangeChild = prepost[level][children[child]]; bestInChild.erase({segtree.query(1, 0, segtree.n-1, rangeChild.first, rangeChild.second), child}); pair<int, int> rangeUpdate = prepost[level][v]; segtree.update(1, 0, segtree.n-1, rangeUpdate.first, rangeUpdate.second, x); bestInChild.insert({segtree.query(1, 0, segtree.n-1, rangeChild.first, rangeChild.second), child}); } int getDiam() { if (bestInChild.empty()) return 0; if (bestInChild.size()==1) return (*bestInChild.rbegin()).first; return (*bestInChild.rbegin()).first + (*next(bestInChild.rbegin())).first; } pair<int, vector<int>> init(int v, int _level, int forbidden) { level = _level; currCol = 0; order.clear(); dfs(v, -1, forbidden); int centroid = findCentroid(v, -1, forbidden); currCol = 0; order.clear(); verticies.clear(); children.clear(); dfs(centroid, -1, forbidden); segtree.init(order.size(), vector<int>()); for (int i = 0; i<(int)children.size(); i++) { auto range = prepost[level][children[i]]; bestInChild.insert({segtree.query(1, 0, segtree.n-1, range.first, range.second), i}); } return {centroid, children}; } }; int N, Q, W; vector<tree> trees; vector<vector<int>> inTrees; set<pair<int, int>> allDiams; // len, treeInd void makeTrees() { queue<array<int, 3>> q; // centroid, level, parent; q.push({0, 0, -1}); while (q.size()) { tree x; auto newComps = x.init(q.front()[0], q.front()[1], q.front()[2]); centroidLevel[newComps.first] = q.front()[1]; for (int i: newComps.second) { q.push({i, q.front()[1]+1, newComps.first}); } q.pop(); for (int i: x.verticies) inTrees[i].push_back(trees.size()); allDiams.insert({0, trees.size()}); trees.push_back(x); } } void updateEdge(int u, int v, int x) { int p1 = 0; int p2 = 0; while (p1<(int)inTrees[u].size() && p2<(int)inTrees[v].size()) { if (inTrees[u][p1] == inTrees[v][p2]) { allDiams.erase({trees[inTrees[u][p1]].getDiam(), inTrees[u][p1]}); trees[inTrees[u][p1]].updateEdge(u, v, x); allDiams.insert({trees[inTrees[u][p1]].getDiam(), inTrees[u][p1]}); p1++; p2++; continue; } if (inTrees[u][p1] < inTrees[v][p2]) { p1++; continue; } p2++; } } int queryBest() { return (*allDiams.rbegin()).first; } signed main() { cin.tie(0); ios_base::sync_with_stdio(0); cin >> N >> Q >> W; graph.resize(N); inTrees.resize(N); centroidLevel.assign(N, -1); vector<array<int,3>> edges(N-1); for (int i = 0; i<N-1; i++) { int a, b, c; cin >> a >> b >> c; a--; b--; edges[i] = {a, b, c}; graph[a].push_back(b); graph[b].push_back(a); } makeTrees(); for (auto i: edges) { updateEdge(i[0], i[1], i[2]); } int last = 0; for (int i = 0; i<Q; i++) { int _d, _e; cin >> _d >> _e; int d = (_d+last)%(N-1); int e = (_e+last)%(W); int diff = e-edges[d][2]; updateEdge(edges[d][0], edges[d][1], diff); edges[d][2] = e; last = queryBest(); 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...