제출 #266970

#제출 시각아이디문제언어결과실행 시간메모리
266970johuthaDynamic Diameter (CEOI19_diameter)C++17
31 / 100
5049 ms225960 KiB
#include <iostream> #include <vector> #include <set> #define int long long #define log2(x) (sizeof(long long)*8 - __builtin_clzll(x)) using namespace std; struct segtree { vector<int> table; vector<int> ops; void apply(int pos, int val) { ops[pos] += val; table[pos] += val; } void propagate(int pos) { apply(2*pos + 1, ops[pos]); apply(2*pos + 2, ops[pos]); ops[pos] = 0; } int query(int ql, int qr, int l, int r, int pos) { if (ql <= l && r <= qr) return table[pos]; if (r < ql || qr < l) return -1; propagate(pos); return max(query(ql, qr, l, (l + r)/2, 2*pos + 1), query(ql, qr, (l + r)/2 + 1, r, 2*pos + 2)); } void update(int ql, int qr, int val, int l, int r, int pos) { if (ql <= l && r <= qr) { apply(pos, val); return; } if (r < ql || qr < l) return; propagate(pos); update(ql, qr, val, l, (l + r)/2, 2*pos + 1); update(ql, qr, val, (l + r)/2 + 1, r, 2*pos + 2); table[pos] = max(table[2*pos + 1], table[2*pos + 2]); } void build(const vector<int>& vs, int l, int r, int pos) { if (l == r) { table[pos] = vs[l]; return; } build(vs, l, (l + r)/2, 2*pos + 1); build(vs, (l + r)/2 + 1, r, 2*pos + 2); table[pos] = max(table[2*pos + 1], table[2*pos + 2]); } }; struct tree { int n; int logn; vector<vector<pair<int,int>>> adjlist; vector<vector<int>> prein; vector<vector<int>> preout; vector<vector<int>> root; vector<vector<int>> desc; vector<vector<int>> depth; vector<int> sz; vector<multiset<int, greater<int>>> tvals; vector<segtree> trees; multiset<int, greater<int>> mvals; vector<int> lvl; vector<pair<int,int>> edges; vector<int> weights; int getmx(int ms) { return (*tvals[ms].begin()) + (*next(tvals[ms].begin())); } int update(int ind, int val) { auto vp = edges[ind]; int mlv = min(lvl[vp.first], lvl[vp.second]); int nd = val - weights[ind]; weights[ind] = val; for (int i = 0; i <= mlv; i++) { int v = (depth[vp.first][i] < depth[vp.second][i] ? vp.second : vp.first); int rt = root[v][i]; mvals.erase(mvals.find(getmx(rt))); int dsc = desc[v][i]; int sv = trees[rt].query(prein[dsc][i], preout[dsc][i], 0, sz[rt] - 1, 0); tvals[rt].erase(tvals[rt].find(sv)); trees[rt].update(prein[v][i], preout[v][i], nd, 0, sz[rt] - 1, 0); sv = trees[rt].query(prein[dsc][i], preout[dsc][i], 0, sz[rt] - 1, 0); tvals[rt].insert(sv); mvals.insert(getmx(rt)); } return *mvals.begin(); } void prefdfs(int curr, int par, int lv, int& ord, int dsc, int dpth, vector<int>& dsts, int dist, int rt) { if (lvl[curr] < lv) return; root[curr][lv] = rt; prein[curr][lv] = ord; desc[curr][lv] = dsc; depth[curr][lv] = dpth; dsts.push_back(dist); ord++; for (auto np : adjlist[curr]) { int next = np.first; if (next == par) continue; prefdfs(next, curr, lv, ord, (dsc == -1 ? next : dsc), dpth + 1, dsts, dist + np.second, rt); } preout[curr][lv] = ord - 1; } void precalcdia() { logn = log2(n); prein.resize(n, vector<int>(logn, -1)); preout.resize(n, vector<int>(logn, -1)); root.resize(n, vector<int>(logn, -1)); desc.resize(n, vector<int>(logn, -1)); depth.resize(n, vector<int>(logn, -1)); sz.resize(n, -1); tvals.resize(n); trees.resize(n); lvl.resize(n, -1); for (int i = 0; i < n; i++) { vector<int> ds; int ord = 0; int lv = lvl[i]; prefdfs(i, -1, lv, ord, -1, 0, ds, 0, i); trees[i].table.resize(4*ord, -1); trees[i].ops.resize(4*ord, 0); trees[i].build(ds, 0, ord - 1, 0); tvals[i].insert(0); tvals[i].insert(0); sz[i] = ord; for (auto np : adjlist[i]) { int next = np.first; if (lvl[next] < lv) continue; int sv = trees[i].query(prein[next][lv], preout[next][lv], 0, ord - 1, 0); tvals[i].insert(sv); } mvals.insert(getmx(i)); } } vector<int> ssz; int szdfs(int curr, int par) { if (lvl[curr] != -1) return 0; ssz[curr] = 1; for (auto np : adjlist[curr]) { int next = np.first; if (next == par) continue; ssz[curr] += szdfs(next, curr); } return ssz[curr]; } int cntdfs(int curr, int par, int sbz) { for (auto np : adjlist[curr]) { int next = np.first; if (next == par || lvl[next] != -1) continue; if (ssz[next] > sbz / 2) return cntdfs(next, curr, sbz); } return curr; } void findcentroid(int nrt, int lv) { szdfs(nrt, -1); int cent = cntdfs(nrt, -1, ssz[nrt]); lvl[cent] = lv; for (auto np : adjlist[cent]) { int next = np.first; if (lvl[next] == -1) findcentroid(next, lv + 1); } } void precalc() { lvl.resize(n, - 1); ssz.resize(n, -1); findcentroid(0, 0); precalcdia(); // print(); } }; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, q, m; cin >> n >> q >> m; tree t; t.n = n; t.adjlist.resize(n); t.edges.resize(n - 1); t.weights.resize(n - 1); for (int i = 0; i < n - 1; i++) { int a, b, w; cin >> a >> b >> w; a--; b--; t.edges[i] = make_pair(a, b); t.weights[i] = w; t.adjlist[a].emplace_back(b, w); t.adjlist[b].emplace_back(a, w); } t.precalc(); int last = 0; for (int i = 0; i < q; i++) { int d, e; cin >> d >> e; d = (d + last) % (n - 1); e = (e + last) % m; last = t.update(d, e); cout << last << "\n"; } }
#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...