이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// Author: Ivan Teo
// Created: Sun Jun 23 11:05:28 2024
#define TASKNAME "1192B"
#include <bits/stdc++.h>
using namespace std;
#define fore(i, a, b) for (int i = (a); i <= (b); i++)
#define int long long
using vi = vector<int>;
using ii = pair<int, int>;
#define pb emplace_back
#define fi first
#define se second
#define sz(v) ((int)v.size())
#define all(v) v.begin() + 1, v.end()
#define alll(v) v.begin(), v.end()
#define db(x) cerr << "[" << #x << " = " << x << "]"
#define el cerr << "\n=========================================\n"
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r)
{
assert(l <= r);
return uniform_int_distribution<int> (l, r)(rng);
}
#define idl (id << 1)
#define idr (id << 1 | 1)
struct SegmentTree
{
int n;
vector<ii> st;
vi lz;
SegmentTree() {}
SegmentTree(int n): n(n), st(4 * n + 5), lz(4 * n + 5)
{
build(1, 1, n);
}
void add(int id, int v)
{
st[id].fi += v;
lz[id] += v;
}
void push(int id)
{
add(idl, lz[id]);
add(idr, lz[id]);
lz[id] = 0;
}
void build(int id, int l, int r)
{
if (l > r) return ;
if (l == r) return (void)(st[id] = {0, l});
int m = l + r >> 1;
build(idl, l, m);
build(idr, m + 1, r);
st[id] = max(st[idl], st[idr]);
}
void add(int id, int l, int r, int tl, int tr, int v)
{
if (l > r || l > tr || r < tl) return ;
if (l >= tl && r <= tr) return (void)(add(id, v));
push(id);
int m = l + r >> 1;
add(idl, l, m, tl, tr, v);
add(idr, m + 1, r, tl, tr, v);
st[id] = max(st[idl], st[idr]);
}
ii get(int id, int l, int r, int tl, int tr)
{
if (l > r || l > tr || r < tl) return {};
if (l >= tl && r <= tr) return st[id];
push(id);
int m = l + r >> 1;
return max(get(idl, l, m, tl, tr), get(idr, m + 1, r, tl, tr));
}
void add(int l, int r, int v)
{
add(1, 1, n, l, r, v);
}
ii get(int l, int r)
{
return get(1, 1, n, l, r);
}
ii get()
{
return st[1];
}
};
using iii = tuple<int, int, int>;
struct Tree
{
vector<iii> e;
vector<vector<ii>> g;
vi dep, branch, in, out, pw, l, inv;
SegmentTree st;
int n, root, timer = 0;
set<ii> s;
Tree() {}
Tree(vector<iii> e, int root): e(e), root(root)
{
build();
}
void dfs(int u, int p)
{
in[u] = ++timer;
inv[timer] = u;
if (p == root) branch[u] = u;
else if (u != root) branch[u] = branch[p];
for (auto &[v, w] : g[u]) if (v != p)
{
dep[v] = dep[u] + w;
pw[v] = w;
dfs(v, u);
}
out[u] = timer;
}
void build()
{
for (auto &[u, v, w] : e) l.pb(u), l.pb(v);
sort(alll(l));
l.erase(unique(alll(l)), l.end());
n = sz(l);
g = vector<vector<ii>>(n + 1);
inv = pw = in = out = dep = branch = vi(n + 1);
st = SegmentTree(n);
for (auto &[u, v, w] : e)
{
s.insert({u, v});
s.insert({v, u});
u = lower_bound(alll(l), u) - l.begin() + 1;
v = lower_bound(alll(l), v) - l.begin() + 1;
g[u].pb(v, w);
g[v].pb(u, w);
}
root = lower_bound(alll(l), root) - l.begin() + 1;
dfs(root, 0);
fore(i, 1, n) st.add(in[i], in[i], dep[i]);
}
void upd(int u, int v, int w)
{
if (s.find(ii(u, v)) == s.end()) return ;
u = lower_bound(alll(l), u) - l.begin() + 1;
v = lower_bound(alll(l), v) - l.begin() + 1;
if (in[u] > in[v]) swap(u, v);
st.add(in[v], out[v], w - pw[v]);
pw[v] = w;
}
int get()
{
auto [dist, u] = st.get();
u = inv[u];
dist += max(st.get(1, in[branch[u]] - 1).fi, st.get(out[branch[u]] + 1, n).fi);
return dist;
}
};
void solve()
{
int n, q, W;
cin >> n >> q >> W;
vector<vector<ii>> g(n + 1);
vector<ii> edge;
fore(i, 1, n - 1)
{
int u, v, w;
cin >> u >> v >> w;
g[u].pb(v, w);
g[v].pb(u, w);
edge.pb(u, v);
}
vi sz = vi(n + 1), del(n + 1);
function<int(int, int, int)> centroid = [&](int u, int p, int n)
{
for (auto &[v, w] : g[u]) if (!del[v] && v != p)
if (sz[v] * 2 > n) return centroid(v, u, n);
return u;
};
function<void(int, int)> dfs = [&](int u, int p)
{
sz[u] = 1;
for (auto &[v, w] : g[u]) if (!del[v] && v != p)
dfs(v, u), sz[u] += sz[v];
};
vector<iii> e;
function<void(int, int)> add = [&](int u, int p)
{
for (auto &[v, w] : g[u]) if (!del[v] && v != p)
add(v, u), e.pb(u, v, w);
};
vector<Tree> jungle;
function<void(int)> go = [&](int u)
{
dfs(u, 0);
int root = centroid(u, 0, sz[u]);
del[root] = 1;
e.clear();
add(root, 0);
if (sz(e)) jungle.pb(Tree(e, root));
for (auto &[v, w] : g[root]) if (!del[v])
go(v);
};
go(1);
int last = 0;
while (q--)
{
int id, w;
cin >> id >> w;
id = (id + last) % (n - 1);
w = (w + last) % W;
// db(edge[id].fi), db(edge[id].se), db(w), el;
int ans = 0;
for (auto &i : jungle) i.upd(edge[id].fi, edge[id].se, w), ans = max(ans, i.get());
cout << ans << '\n';
last = ans;
}
}
signed main()
{
cin.tie(0)->sync_with_stdio(0);
if (fopen(TASKNAME ".inp", "r"))
{
freopen(TASKNAME ".inp", "r", stdin);
freopen(TASKNAME ".out", "w", stdout);
}
int tc = 1;
// cin >> tc;
while (tc--) solve();
el, cerr << "Execution Time: " << 1.0 * clock() / CLOCKS_PER_SEC << "s", el;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
diameter.cpp: In member function 'void SegmentTree::build(long long int, long long int, long long int)':
diameter.cpp:58:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
58 | int m = l + r >> 1;
| ~~^~~
diameter.cpp: In member function 'void SegmentTree::add(long long int, long long int, long long int, long long int, long long int, long long int)':
diameter.cpp:69:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
69 | int m = l + r >> 1;
| ~~^~~
diameter.cpp: In member function 'ii SegmentTree::get(long long int, long long int, long long int, long long int, long long int)':
diameter.cpp:80:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
80 | int m = l + r >> 1;
| ~~^~~
diameter.cpp: In function 'int main()':
diameter.cpp:247:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
247 | freopen(TASKNAME ".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:248:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
248 | freopen(TASKNAME ".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |