이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 11;
typedef pair<int, int> ii;
int n, q, w;
int a[N];
int cost[N];
ii E[N];
vector<int> adj[N], pos[N];
int top = 0;
void dfs(int u, int id_edge, int p = 0) {
for (int id : adj[u]) {
int x = E[id].first, y = E[id].second;
if (x == u) swap(x, y);
if (x == p) continue;
a[++top] = cost[id];
pos[id].push_back(top);
dfs(x, id, u);
}
if (p) {
a[++top] = -cost[id_edge];
pos[id_edge].push_back(top);
}
}
struct Node {
int pfix, sfix; // pfix get maximum prefix sum, sfix get maximum -suffix sum
int ans_pre, ans_suf; // f but ans_pre touch left, ans_suf touch right
int all; // f but touch left and touch right
int sum, f;
Node(){}
};
Node Seg[4 * N];
void merge(int node) {
Seg[node].pfix = max(Seg[node * 2].pfix, Seg[node * 2].sum + Seg[node * 2 + 1].pfix);
Seg[node].sfix = max(Seg[node * 2 + 1].sfix, -Seg[node * 2 + 1].sum + Seg[node * 2].sfix);
Seg[node].sum = Seg[node * 2].sum + Seg[node * 2 + 1].sum;
Seg[node].all = max(Seg[node * 2].all + Seg[node * 2 + 1].sum, -Seg[node * 2].sum + Seg[node * 2 + 1].all);
Seg[node].ans_pre = max(max(Seg[node * 2].ans_pre, Seg[node * 2].all + Seg[node * 2 + 1].pfix), -Seg[node * 2].sum + Seg[node * 2 + 1].ans_pre);
Seg[node].ans_suf = max(max(Seg[node * 2 + 1].ans_suf, Seg[node * 2 + 1].all + Seg[node * 2].sfix), Seg[node * 2 + 1].sum + Seg[node * 2].ans_suf);
Seg[node].f = max(Seg[node * 2].f, Seg[node * 2 + 1].f);
Seg[node].f = max(Seg[node].f, Seg[node * 2].ans_suf + Seg[node * 2 + 1].pfix);
Seg[node].f = max(Seg[node].f, Seg[node * 2].sfix + Seg[node * 2 + 1].ans_pre);
}
void build(int node, int l, int r) {
if (l == r) {
Seg[node].pfix = max(0, a[l]); Seg[node].sfix = max(0, -a[l]);
Seg[node].f = Seg[node].ans_pre = Seg[node].ans_suf = Seg[node].all = abs(a[l]);
Seg[node].sum = a[l];
return;
}
int mi = (l + r) / 2;
build(node * 2, l, mi);
build(node * 2 + 1, mi + 1, r);
merge(node);
return;
}
void upd(int node, int l, int r, int pos) {
if (l == r) {
Seg[node].pfix = max(0, a[l]); Seg[node].sfix = max(0, -a[l]);
Seg[node].f = Seg[node].ans_pre = Seg[node].ans_suf = Seg[node].all = abs(a[l]);
Seg[node].sum = a[l];
return;
}
int mi = (l + r) / 2;
if (pos <= mi) upd(node * 2, l, mi, pos);
else upd(node * 2 + 1, mi + 1, r, pos);
merge(node);
return;
}
int main(int argc, char** argv) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> q >> w;
for (int i = 0; i < n - 1; i++) {
int u, v, c;
cin >> u >> v >> cost[i];
E[i] = ii(u, v);
adj[u].emplace_back(i);
adj[v].emplace_back(i);
}
dfs(1, -1);
build(1, 1, 2 * (n - 1));
int last = 0;
while (q--) {
int d, e; cin >> d >> e;
d = (d + last) % (n - 1);
e = (e + last) % w;
a[pos[d][0]] = e;
upd(1, 1, 2 * (n - 1), pos[d][0]);
a[pos[d][1]] = -e;
upd(1, 1, 2 * (n - 1), pos[d][1]);
last = Seg[1].f;
cout << last << '\n';
}
}
컴파일 시 표준 에러 (stderr) 메시지
diameter.cpp: In function 'int main(int, char**)':
diameter.cpp:97:13: warning: unused variable 'c' [-Wunused-variable]
97 | int u, v, c;
| ^
# | 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... |