이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define sz(x) int(x.size())
using ll = long long;
const ll INF = 1e18 + 10;
template<class T> using V = vector<T>;
using vi = V<int>;
using pi = pair<int, int>;
using vpi = V<pi>;
using vl = V<ll>;
struct T {
ll a, b, c, ab, bc, abc;
T() { a = b = c = ab = bc = abc = -INF; }
T(int x) {
a = x, b = -2 * x, c = x, ab = -x, bc = -x, abc = 0;
}
void upd(int d) {
a += d, b -= 2 * d, c += d, ab -= d, bc -= d;
}
};
struct Seg {
const T ID = T(); T comb(T a, T b) {
T c = T();
c.a = max(a.a, b.a), c.b = max(a.b, b.b), c.c = max(a.c, b.c);
c.ab = max({a.ab, b.ab, a.a + b.b}), c.bc = max({a.bc, b.bc, a.b + b.c});
c.abc = max({a.abc, b.abc, a.ab + b.c, a.a + b.bc});
return c;
};
V<T> seg; vl lazy; int N; void init(int n) {
for(N = 1; N < n; ) N *= 2;
seg.assign(2 * N, ID); lazy.assign(2 * N, 0);
}
void push(int x, int L, int R) {
seg[x].upd(lazy[x]);
if (L != R) for(int i = 0; i < 2; i++) lazy[2*x+i] += lazy[x];
lazy[x] = 0;
}
void set(int p, T x) {
seg[p += N] = x; for(p /= 2; p; p /= 2) pull(p);
}
void pull(int x) { seg[x] = comb(seg[2*x], seg[2*x+1]); }
void upd(int l, int r, int v, int x, int L, int R) {
push(x, L, R); if (r < L || R < l) return;
if (l <= L && R <= r) {
lazy[x] += v; push(x, L, R); return;
}
int M = (L + R) / 2;
upd(l, r, v, 2 * x, L, M);
upd(l, r, v, 2 * x + 1, M + 1, R);
pull(x);
}
void upd(int l, int r, int v) { upd(l, r, v, 1, 0, N - 1); }
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int N, M; ll MXW; cin >> N >> M >> MXW;
V<vpi> adj(N); vi E(N - 1); vl W(N);
for(int i = 0; i < N - 1; i++) {
int u, v; cin >> u >> v >> W[i]; --u, --v;
adj[u].pb(mp(v, i));
adj[v].pb(mp(u, i));
}
Seg S; S.init(2*N); vi st(N), en(N);
vi ord; int t = 0; ll dep = 0;
function<void(int, int)> dfs = [&](int u, int p) {
st[u] = en[u] = t; S.set(t, T(dep)); ord.pb(u); t++;
for(auto& e : adj[u]) {
int v, i; tie(v, i) = e;
if (v == p) continue;
dep += W[i];
E[i] = v; dfs(v, u);
dep -= W[i];
S.set(t, T(dep)); en[u] = t; ord.pb(u); t++;
}
};
dfs(0, -1);
// for(int i = 0; i < N; i++) {
// cout << i << " => " << st[i] << " " << en[i] << endl;
// }
// for(auto& x : ord) {
// cout << x << " ";
// }
// cout << endl;
// cout << S.seg[1].abc << endl;
ll last = 0;
for(int i = 0; i < M; i++) {
ll e, w; cin >> e >> w;
e = ll(e + last) % ll(N - 1);
w = ll(w + last) % MXW;
// cout << e << " " << w << endl;
int u = E[e];
S.upd(st[u], en[u], w - W[e]);
W[e] = w;
last = S.seg[1].abc;
cout << last << nl;
}
exit(0-0);
}
# | 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... |