QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #469765 | #7563. Fun on Tree | duckindog | TL | 3751ms | 39088kb | C++23 | 2.2kb | 2024-07-09 23:42:57 | 2024-07-09 23:42:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 200'000 + 10;
int n, q;
int a[N];
int par[N];
vector<pair<int, int>> ad[N];
int d[N], st[N], rvs[N], ed[N], it;
void dfs0(int u) {
st[u] = ++it; rvs[it] = u;
for (const auto& [v, w] : ad[u]) {
d[v] = d[u] + w;
par[v] = u;
dfs0(v);
}
ed[u] = it;
}
pair<int, int> f[N << 2];
int lazy[N << 2];
void build(int s, int l, int r) {
if (l == r) {
f[s].first = d[rvs[l]] - a[rvs[l]];
f[s].second = -rvs[l];
return;
}
int mid = l + r >> 1;
build(s << 1, l, mid); build(s << 1 | 1, mid + 1, r);
f[s] = max(f[s << 1], f[s << 1 | 1]);
}
void push(int s) {
f[s << 1].first += lazy[s]; f[s << 1 | 1].first += lazy[s];
lazy[s << 1] += lazy[s]; lazy[s << 1 | 1] += lazy[s];
lazy[s] = 0;
}
void update(int s, int l, int r, int u, int v, int x) {
if (v < l || u > r) return;
if (u <= l && r <= v) {
f[s].first += x;
lazy[s] += x;
return;
}
push(s);
int mid = l + r >> 1;
update(s << 1, l, mid, u, v, x); update(s << 1 | 1, mid + 1, r, u, v, x);
f[s] = max(f[s << 1], f[s << 1 | 1]);
}
pair<int, int> query(int s, int l, int r, int u, int v) {
if (v < l || u > r) return {-1'000'000'000'000'000, 0};
if (u <= l && r <= v) return f[s];
push(s);
int mid = l + r >> 1;
return max(query(s << 1, l, mid, u, v), query(s << 1 | 1, mid + 1, r, u, v));
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> q;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int v = 2; v <= n; ++v) {
int u, w; cin >> u >> w;
ad[u].push_back({v, w});
}
dfs0(par[1] = 1);
build(1, 1, n);
while (q--) {
int x, y, v; cin >> x >> y >> v;
int start = x;
update(1, 1, n, st[y], ed[y], -v);
pair<int, int> answer = query(1, 1, n, st[x], ed[x]);
answer.first -= d[x];
while (true) {
int u = par[x];
if (x == 1) break;
auto ret = max(query(1, 1, n, st[u], st[x] - 1), query(1, 1, n, ed[x] + 1, ed[u]));
ret.first += d[start] - 2 * d[u];
answer = max(answer, ret);
x = u;
}
cout << -answer.second << " " << answer.first << "\n";
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 9884kb
input:
6 6 1 1 4 5 1 4 1 5 2 0 3 2 4 1 5 6 3 2 -100000 1 2 100000 1 1 0 2 2 66 3 1 5 4 4 -3
output:
6 100005 6 10 6 10 1 4 1 -1 1 1
result:
ok 6 lines
Test #2:
score: 0
Accepted
time: 2ms
memory: 13972kb
input:
5 6 -10 0 2 -4 8 1 7 1 1 2 2 2 -2 1 1 100 2 1 -100 1 1 0 4 3 10 2 5 3 5 2 2
output:
4 -87 1 17 4 13 1 19 1 17 1 15
result:
ok 6 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 11800kb
input:
6 3 0 0 0 0 0 0 1 10 1 10 1 -100 4 10 4 11 1 1 0 4 1 0 1 4 1000
output:
2 10 6 11 2 10
result:
ok 3 lines
Test #4:
score: 0
Accepted
time: 1ms
memory: 11792kb
input:
2 0 1 1 1 3
output:
result:
ok 0 lines
Test #5:
score: 0
Accepted
time: 873ms
memory: 36756kb
input:
200000 200000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 ...
output:
119017 15000000000 120167 17000000000 119017 15000000000 119017 15000000000 120167 17000000000 120167 15000000000 120167 16000000000 119017 17000000000 119017 16000000000 119017 12000000000 119017 17000000000 120167 16000000000 120167 14000000000 120167 17000000000 120167 18000000000 120167 16000000...
result:
ok 200000 lines
Test #6:
score: 0
Accepted
time: 3458ms
memory: 38460kb
input:
200000 200000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 ...
output:
169355 88000000000 171273 95000000000 171273 100000000000 169355 88000000000 169355 93000000000 169355 97000000000 169355 93000000000 171273 78000000000 171273 86000000000 169355 90000000000 169355 84000000000 169355 80000000000 169355 78000000000 171273 84000000000 169355 89000000000 171273 8400000...
result:
ok 200000 lines
Test #7:
score: 0
Accepted
time: 878ms
memory: 36872kb
input:
200000 200000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 ...
output:
60406 17000000000 163359 19000000000 163359 18000000000 163359 17000000000 163359 18000000000 60406 17000000000 163359 16000000000 60406 16000000000 60406 18000000000 163359 17000000000 163359 16000000000 163359 15000000000 163359 18000000000 163359 16000000000 60406 13000000000 163359 15000000000 6...
result:
ok 200000 lines
Test #8:
score: 0
Accepted
time: 3367ms
memory: 39088kb
input:
200000 200000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 ...
output:
158239 95000000000 170228 90000000000 170228 91000000000 158239 97000000000 158239 90000000000 170228 97000000000 170228 95000000000 158239 89000000000 170228 84000000000 158239 97000000000 158239 88000000000 170228 81000000000 158239 89000000000 170228 84000000000 170228 84000000000 158239 83000000...
result:
ok 200000 lines
Test #9:
score: 0
Accepted
time: 854ms
memory: 35944kb
input:
200000 200000 -999999197 -999999547 -999999355 -999999799 -999999360 -999999720 -999999365 -999999419 -999999958 -999999574 -999999169 -999999422 -999999695 -999999971 -999999820 -999999822 -999999107 -999999420 -999999519 -999999970 -999999601 -999999521 -999999134 -999999638 -999999338 -999999570 ...
output:
2841 999999254 109445 999999369 58340 999999315 117049 999999782 118472 999999076 24148 999999131 47844 999999290 113056 999999668 46680 999999228 109091 999999634 68365 999999666 156304 999999674 39689 999999729 103343 999999322 123506 999999661 189258 999999210 142816 999999890 88985 999999626 120...
result:
ok 200000 lines
Test #10:
score: 0
Accepted
time: 3677ms
memory: 38212kb
input:
200000 200000 -999999902 -999999301 -999999682 -999999655 -999999078 -999999674 -999999335 -999999307 -999999892 -999999582 -999999768 -999999854 -999999299 -999999298 -999999510 -999999440 -999999916 -999999930 -999999447 -999999825 -999999586 -999999447 -999999186 -999999634 -999999258 -999999756 ...
output:
43055 999999140 49534 999999915 34106 999999771 160878 999999227 148508 999999679 72994 999999134 163193 999999850 63938 999999143 54880 999999740 52045 999999113 26995 999999039 87143 999999281 74906 999999554 172131 999999137 138024 999999394 57682 999999637 62669 999999051 81932 999999518 33406 9...
result:
ok 200000 lines
Test #11:
score: 0
Accepted
time: 914ms
memory: 37220kb
input:
200000 200000 -999999602 -999999216 -999999710 -999999943 -999999715 -999999936 -999999594 -999999877 -999999394 -999999644 -999999110 -999999223 -999999342 -999999960 -999999730 -999999642 -999999058 -999999863 -999999406 -999999319 -999999812 -999999634 -999999519 -999999599 -999999799 -999999846 ...
output:
183067 999999909 99888 999999736 7724 999999364 161568 999999298 93017 999999903 105263 999999788 62219 999999053 132842 999999223 45435 999999362 159394 999999759 25951 999999780 118834 999999191 154586 999999744 82508 999999076 164452 999999372 100552 999999562 155126 999999332 100719 999999406 19...
result:
ok 200000 lines
Test #12:
score: 0
Accepted
time: 3751ms
memory: 38784kb
input:
200000 200000 -999999723 -999999956 -999999679 -999999610 -999999755 -999999845 -999999359 -999999914 -999999060 -999999981 -999999093 -999999136 -999999983 -999999772 -999999112 -999999777 -999999827 -999999612 -999999413 -999999471 -999999757 -999999293 -999999685 -999999999 -999999791 -999999170 ...
output:
99717 999999755 15526 999999972 23346 999999932 42421 999999452 2286 999999049 193610 999999232 70168 999999164 26214 999999570 138962 999999287 155319 999999407 47662 999999714 111146 999999883 120662 999999304 98100 999999670 27642 999999638 20252 999999486 87487 999999101 177165 999999970 195686 ...
result:
ok 200000 lines
Test #13:
score: -100
Time Limit Exceeded
input:
200000 200000 4 0 2 8 -2 -3 -10 7 -4 -8 -2 10 9 9 -9 -5 -7 -2 6 1 -9 -1 -5 0 2 0 9 1 -9 1 7 -1 -5 -8 -9 1 6 -1 7 -2 9 -10 9 -7 6 9 -3 -2 -4 0 -4 -2 10 -3 -8 2 -1 3 -8 -7 -4 5 -9 5 -7 8 -7 -8 -3 6 3 -8 1 -10 0 -3 3 7 10 4 4 -4 -6 -7 -5 -5 -4 6 -5 -7 -2 -5 9 0 8 10 7 -5 -7 -5 7 10 2 -7 -8 9 1 1 -6 8 -...
output:
189813 1486 189813 1227 31620 1530 31620 935 189813 917 189813 1403 189813 1394 31620 1303 189813 1096 189813 1287 189813 1298 189813 1322 189813 1167 31620 1527 189813 1337 31620 1313 189813 1393 189813 854 189813 1271 31620 1459 31620 806 189813 1076 189813 1148 189813 1300 189813 1282 189813 1265...