| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 834593 | Elias | Dynamic Diameter (CEOI19_diameter) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#ifndef _DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define ll int64_t
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
{
pair<ll, 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<ll> &a)
{
n = a.size();
updates = vector<ll>(4 * n);
b = vector<pair<ll, int>>(4 * n);
build(0, n, 0, a);
}
SegTree() {}
private:
int n = 0;
vector<pair<ll, int>> b = {};
vector<ll> 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].first += updates[i];
b[i * 2 + 2].first += updates[i];
updates[i] = 0;
}
pair<ll, int> build(int l, int r, int i, const vector<ll> &a)
{
if (l + 1 == r)
return b[i] = pair<ll, int>{a[l], l};
int m = (l + r) / 2;
return b[i] = max(build(l, m, i * 2 + 1, a), build(m, r, i * 2 + 2, a));
}
pair<ll, int> get(int l, int r, int i, int ql, int qr)
{
if (l >= qr || r <= ql)
return {LLONG_MIN / 2, -1};
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));
}
pair<ll, 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].first += 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;
unordered_map<int, vector<pair<int, ll>>> edges;
unordered_map<int, int> pre;
unordered_map<int, int> subtree;
unordered_map<int, int> initial_parent;
vector<int> pre_order;
vector<ll> 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, unordered_map<int, vector<pair<int, ll>>> &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, ll d = 0, int p = -1)
{
pre[i] = timer++;
pre_order.push_back(i);
pre_dist[pre[i]] = d;
int subtree_size = 1;
if (p == -1)
initial_parent[i] = -1;
else if (initial_parent[p] == -1)
initial_parent[i] = i;
else
initial_parent[i] = initial_parent[p];
for (auto [c, D] : edges[i])
{
if (c != p)
{
subtree_size += dfs(c, d + D, i);
}
}
subtree[i] = subtree_size;
return subtree_size;
}
vector<unordered_map<int, vector<pair<int, ll>>>> split()
{
vector<unordered_map<int, vector<pair<int, ll>>>> out;
for (auto [c, d] : edges[centroid])
{
unordered_map<int, vector<pair<int, ll>>> subset;
get_edges(c, centroid, subset);
out.push_back(move(subset));
}
return out;
}
Tree(unordered_map<int, vector<pair<int, ll>>> edges) : edges{edges}
{
n = edges.size();
pre_dist = vector<ll>(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);
}
ll update(int a, int b, int c)
{
if (subtree.count(a) != 0 && subtree.count(b) != 0)
{
if (pre[a] > pre[b])
swap(a, b);
ll dist_lower = pre_dist_seg.get(pre[b], pre[b] + 1).first;
ll dist_upper = pre_dist_seg.get(pre[a], pre[a] + 1).first;
ll old_weight = dist_lower - dist_upper;
ll delta = c - old_weight;
pre_dist_seg.inc(pre[b], pre[b] + subtree[b], delta);
}
auto [dist, i] = pre_dist_seg.get(0, n);
int bad_child = initial_parent[pre_order[i]];
auto dist2 = pre_dist_seg.get(0, pre[bad_child]).first;
auto dist3 = pre_dist_seg.get(pre[bad_child] + subtree[bad_child], n).first;
return dist + max({dist2, dist3, 0ll});
}
};
signed main()
{
cin.tie(0);
ios_base::sync_with_stdio(false);
int n, q, w;
cin >> n >> q >> w;
unordered_map<int, vector<pair<int, ll>>> edges;
vector<pair<int, int>> all_edges;
for (int i = 0; i < n - 1; i++)
{
int a, b;
ll 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);
}
}
}
}
vector<ll> subtree_result(subtrees.size());
set<pair<ll, int>> results;
for (int i = 0; i < subtrees.size(); i++)
{
subtree_result[i] = subtrees[i].update(-1, -1, -1);
results.insert({subtree_result[i], i});
}
ll last = 0;
while (q--)
{
ll d, e;
cin >> d >> e;
d = (d + last) % ll(n - 1);
e = (e + last) % w;
auto [a, b] = all_edges[d];
ll out = 0;
for (int i : trees_using[a])
{
results.erase({subtree_result[i], i});
subtree_result[i] = subtrees[i].update(a, b, e);
results.insert({subtree_result[i], i});
}
out = prev(results.end())->first;
cout << out << "\n";
last = out;
}
}