// 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 = 5e18 + 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 |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
352 KB |
Output is correct |
18 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
352 KB |
Output is correct |
18 |
Correct |
1 ms |
344 KB |
Output is correct |
19 |
Correct |
4 ms |
604 KB |
Output is correct |
20 |
Correct |
3 ms |
604 KB |
Output is correct |
21 |
Correct |
4 ms |
604 KB |
Output is correct |
22 |
Correct |
4 ms |
860 KB |
Output is correct |
23 |
Correct |
7 ms |
2652 KB |
Output is correct |
24 |
Correct |
7 ms |
2648 KB |
Output is correct |
25 |
Correct |
7 ms |
2648 KB |
Output is correct |
26 |
Correct |
12 ms |
3160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
7 ms |
540 KB |
Output is correct |
5 |
Correct |
30 ms |
792 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
9 ms |
600 KB |
Output is correct |
11 |
Correct |
42 ms |
972 KB |
Output is correct |
12 |
Correct |
3 ms |
2648 KB |
Output is correct |
13 |
Correct |
4 ms |
2652 KB |
Output is correct |
14 |
Correct |
4 ms |
2652 KB |
Output is correct |
15 |
Correct |
13 ms |
2832 KB |
Output is correct |
16 |
Correct |
55 ms |
3160 KB |
Output is correct |
17 |
Correct |
63 ms |
38724 KB |
Output is correct |
18 |
Correct |
63 ms |
38852 KB |
Output is correct |
19 |
Correct |
68 ms |
39180 KB |
Output is correct |
20 |
Correct |
81 ms |
38852 KB |
Output is correct |
21 |
Correct |
160 ms |
38848 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
604 KB |
Output is correct |
2 |
Correct |
6 ms |
796 KB |
Output is correct |
3 |
Correct |
25 ms |
1216 KB |
Output is correct |
4 |
Correct |
56 ms |
1284 KB |
Output is correct |
5 |
Correct |
8 ms |
4956 KB |
Output is correct |
6 |
Correct |
16 ms |
4956 KB |
Output is correct |
7 |
Correct |
41 ms |
5208 KB |
Output is correct |
8 |
Correct |
70 ms |
5456 KB |
Output is correct |
9 |
Correct |
35 ms |
19424 KB |
Output is correct |
10 |
Correct |
44 ms |
19492 KB |
Output is correct |
11 |
Correct |
73 ms |
19572 KB |
Output is correct |
12 |
Correct |
113 ms |
19920 KB |
Output is correct |
13 |
Correct |
71 ms |
38344 KB |
Output is correct |
14 |
Correct |
81 ms |
38352 KB |
Output is correct |
15 |
Correct |
122 ms |
38752 KB |
Output is correct |
16 |
Correct |
166 ms |
38856 KB |
Output is correct |
17 |
Correct |
176 ms |
38688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
238 ms |
39344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
352 KB |
Output is correct |
18 |
Correct |
1 ms |
344 KB |
Output is correct |
19 |
Correct |
4 ms |
604 KB |
Output is correct |
20 |
Correct |
3 ms |
604 KB |
Output is correct |
21 |
Correct |
4 ms |
604 KB |
Output is correct |
22 |
Correct |
4 ms |
860 KB |
Output is correct |
23 |
Correct |
7 ms |
2652 KB |
Output is correct |
24 |
Correct |
7 ms |
2648 KB |
Output is correct |
25 |
Correct |
7 ms |
2648 KB |
Output is correct |
26 |
Correct |
12 ms |
3160 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
0 ms |
344 KB |
Output is correct |
29 |
Correct |
1 ms |
344 KB |
Output is correct |
30 |
Correct |
7 ms |
540 KB |
Output is correct |
31 |
Correct |
30 ms |
792 KB |
Output is correct |
32 |
Correct |
0 ms |
348 KB |
Output is correct |
33 |
Correct |
1 ms |
604 KB |
Output is correct |
34 |
Correct |
1 ms |
604 KB |
Output is correct |
35 |
Correct |
1 ms |
604 KB |
Output is correct |
36 |
Correct |
9 ms |
600 KB |
Output is correct |
37 |
Correct |
42 ms |
972 KB |
Output is correct |
38 |
Correct |
3 ms |
2648 KB |
Output is correct |
39 |
Correct |
4 ms |
2652 KB |
Output is correct |
40 |
Correct |
4 ms |
2652 KB |
Output is correct |
41 |
Correct |
13 ms |
2832 KB |
Output is correct |
42 |
Correct |
55 ms |
3160 KB |
Output is correct |
43 |
Correct |
63 ms |
38724 KB |
Output is correct |
44 |
Correct |
63 ms |
38852 KB |
Output is correct |
45 |
Correct |
68 ms |
39180 KB |
Output is correct |
46 |
Correct |
81 ms |
38852 KB |
Output is correct |
47 |
Correct |
160 ms |
38848 KB |
Output is correct |
48 |
Correct |
1 ms |
604 KB |
Output is correct |
49 |
Correct |
6 ms |
796 KB |
Output is correct |
50 |
Correct |
25 ms |
1216 KB |
Output is correct |
51 |
Correct |
56 ms |
1284 KB |
Output is correct |
52 |
Correct |
8 ms |
4956 KB |
Output is correct |
53 |
Correct |
16 ms |
4956 KB |
Output is correct |
54 |
Correct |
41 ms |
5208 KB |
Output is correct |
55 |
Correct |
70 ms |
5456 KB |
Output is correct |
56 |
Correct |
35 ms |
19424 KB |
Output is correct |
57 |
Correct |
44 ms |
19492 KB |
Output is correct |
58 |
Correct |
73 ms |
19572 KB |
Output is correct |
59 |
Correct |
113 ms |
19920 KB |
Output is correct |
60 |
Correct |
71 ms |
38344 KB |
Output is correct |
61 |
Correct |
81 ms |
38352 KB |
Output is correct |
62 |
Correct |
122 ms |
38752 KB |
Output is correct |
63 |
Correct |
166 ms |
38856 KB |
Output is correct |
64 |
Correct |
176 ms |
38688 KB |
Output is correct |
65 |
Incorrect |
238 ms |
39344 KB |
Output isn't correct |
66 |
Halted |
0 ms |
0 KB |
- |