제출 #834447

#제출 시각아이디문제언어결과실행 시간메모리
834447EliasDynamic Diameter (CEOI19_diameter)C++17
0 / 100
5051 ms377780 KiB
#ifndef _DEBUG #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #endif #include <bits/stdc++.h> using namespace std; #define int long long #define all(x) (x).begin(), (x).end() template <class T> istream &operator>>(istream &in, vector<T> &a) { for (T &x : a) in >> x; return in; } template <class T> ostream &operator<<(ostream &out, const vector<T> &a) { for (T x : a) out << x << " "; out << "\n"; return out; } struct SegTree { int get(int l, int r) { return get(0, n, 0, l, r); } void inc(int l, int r, int x) { inc(0, n, 0, l, r, x); } SegTree(const vector<int> &a) { n = a.size(); b = updates = vector<int>(4 * n); build(0, n, 0, a); } SegTree() {} private: int n = 0; vector<int> b = {}; vector<int> updates = {}; void push(int l, int r, int i) { if (l + 1 == r) return; updates[i * 2 + 1] += updates[i]; updates[i * 2 + 2] += updates[i]; b[i * 2 + 1] += updates[i]; b[i * 2 + 2] += updates[i]; updates[i] = 0; } int build(int l, int r, int i, const vector<int> &a) { if (l + 1 == r) return b[i] = a[l]; int m = (l + r) / 2; return b[i] = max(build(l, m, i * 2 + 1, a), build(m, r, i * 2 + 2, a)); } int get(int l, int r, int i, int ql, int qr) { if (l >= qr || r <= ql) return LLONG_MIN / 2; if (l >= ql && r <= qr) return b[i]; push(l, r, i); int m = (l + r) / 2; return max(get(l, m, i * 2 + 1, ql, qr), get(m, r, i * 2 + 2, ql, qr)); } int inc(int l, int r, int i, int ul, int ur, int x) { if (l >= ur || r <= ul) return b[i]; if (l >= ul && r <= ur) { updates[i] += x; b[i] += x; return b[i]; } push(l, r, i); int m = (l + r) / 2; return b[i] = max(inc(l, m, i * 2 + 1, ul, ur, x), inc(m, r, i * 2 + 2, ul, ur, x)); } }; struct Tree { int n; map<int, vector<pair<int, int>>> edges; map<int, int> pre; map<int, int> subtree; vector<int> pre_dist; int timer = 0; int centroid = -1; SegTree pre_dist_seg; int find_centroid(int i, int p = -1) { int subtree_size = 1; int largest_subtree = 0; for (auto [c, D] : edges[i]) { if (c != p) { int sub = find_centroid(c, i); subtree_size += sub; largest_subtree = max(largest_subtree, sub); } } if (largest_subtree <= n / 2 && n - subtree_size <= n / 2) centroid = i; return subtree_size; } void get_edges(int i, int p, map<int, vector<pair<int, int>>> &out) { for (auto [c, d] : edges[i]) { if (c == centroid) continue; out[i].push_back({c, d}); if (c != p) get_edges(c, i, out); } } int dfs(int i, int d = 0, int p = -1) { pre[i] = timer++; pre_dist[pre[i]] = d; int subtree_size = 1; for (auto [c, D] : edges[i]) { if (c != p) { subtree_size += dfs(c, d + D, i); } } subtree[i] = subtree_size; return subtree_size; } vector<map<int, vector<pair<int, int>>>> split() { vector<map<int, vector<pair<int, int>>>> out; for (auto [c, d] : edges[centroid]) { map<int, vector<pair<int, int>>> subset; get_edges(c, centroid, subset); out.push_back(move(subset)); } return out; } Tree(map<int, vector<pair<int, int>>> edges) : edges{edges} { n = edges.size(); pre_dist = vector<int>(n); int start; for (auto [i, c] : edges) { start = i; break; } find_centroid(start); assert(centroid != -1); dfs(centroid); pre_dist_seg = SegTree(pre_dist); } int update(int a, int b, int c) { if (subtree.count(a) == 0 || subtree.count(b) == 0) return 0; if (pre[a] > pre[b]) swap(a, b); int dist_lower = pre_dist_seg.get(pre[b], pre[b] + 1); int dist_upper = pre_dist_seg.get(pre[a], pre[a] + 1); int old_weight = dist_lower - dist_upper; int delta = c - old_weight; pre_dist_seg.inc(pre[b], pre[b] + subtree[b], delta); int largest = 0; int second = 0; for (auto [c, d] : edges[centroid]) { int dist = pre_dist_seg.get(pre[c], pre[c] + subtree[c]); if (dist >= largest) { second = largest; largest = dist; } else if (dist >= second) { second = dist; } } return largest + second; } }; signed main() { cin.tie(0); ios_base::sync_with_stdio(false); int n, q, w; cin >> n >> q >> w; map<int, vector<pair<int, int>>> edges; vector<pair<int, int>> all_edges; for (int i = 0; i < n - 1; i++) { int a, b, c; cin >> a >> b >> c; a--, b--; edges[a].push_back({b, c}); edges[b].push_back({a, c}); all_edges.push_back({a, b}); } vector<Tree> subtrees; subtrees.push_back(Tree(edges)); queue<int> todo; todo.push(0); vector<vector<int>> trees_using(n, {0}); while (todo.size()) { int index = todo.front(); todo.pop(); auto out = subtrees[index].split(); for (auto &x : out) { if (x.size() > 1) { int new_index = subtrees.size(); todo.push(new_index); subtrees.push_back(Tree(x)); for (auto [i, c] : x) { if (trees_using[i].back() != new_index) trees_using[i].push_back(new_index); } } } } int last = 0; while (q--) { int d, e; cin >> d >> e; d = (d + last) % (n - 1); e = (e + last) % w; auto [a, b] = all_edges[d]; int out = 0; for (int i : trees_using[a]) { out = max(out, subtrees[i].update(a, b, e)); } cout << out << "\n"; last = out; } }
#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...