QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#71810 | #946. Magic Tree | He_Ren | 3 | 163ms | 46928kb | C++23 | 2.2kb | 2023-01-12 01:20:54 | 2023-01-12 01:22:54 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 1e5 + 5;
const int MAXP = MAXN * 20;
namespace SegT {
int ls[MAXP], rs[MAXP], pcnt = 0;
ll mx[MAXP], tag[MAXP];
#define lson(u) ls[u],l,mid
#define rson(u) rs[u],mid+1,r
inline void push_up(int u) {
mx[u] = max(mx[ls[u]], mx[rs[u]]);
}
inline void upd(int u, ll k) {
if (!u)
return;
tag[u] += k;
mx[u] += k;
}
inline void push_down(int u) {
if (tag[u]) {
upd(ls[u], tag[u]);
upd(rs[u], tag[u]);
tag[u] = 0;
}
}
void insert(int &u, int l, int r, int q, ll k) {
if (!u)
u = ++pcnt;
if (l == r) {
mx[u] += k;
return;
}
push_down(u);
int mid = (l + r) >> 1;
if (q <= mid)
insert(lson(u), q, k);
else
insert(rson(u), q, k);
push_up(u);
}
void merge(int &u, int l, int r, int v, ll preu, ll prev) {
if (!u && !v)
return;
if (!u) {
upd(u = v, preu);
return;
}
if (!v) {
upd(u, prev);
return;
}
if (l == r) {
mx[u] = max(mx[u], preu) + max(mx[v], prev);
return;
}
push_down(u);
push_down(v);
int mid = (l + r) >> 1;
merge(rson(u), rs[v], max(preu, mx[ls[u]]), max(prev, mx[ls[v]]));
merge(lson(u), ls[v], preu, prev);
push_up(u);
}
int n;
inline void insert(int &u, int q, ll k) {
insert(u, 1, n, q, k);
}
inline void merge(int &u, int v) {
merge(u, 1, n, v, 0, 0);
}
}
vector<int> g[MAXN];
int a[MAXN], b[MAXN];
int rt[MAXN];
void dfs_res(int u) {
for (int v : g[u]) {
dfs_res(v);
SegT::merge(rt[u], rt[v]);
}
if (b[u])
SegT::insert(rt[u], a[u], b[u]);
}
int main(void) {
int n, m, d;
scanf("%d%d%d", &n, &m, &d);
for (int i = 2; i <= n; ++i) {
int j;
scanf("%d", &j);
g[j].push_back(i);
}
for (int i = 1; i <= m; ++i) {
int u, x, y;
scanf("%d%d%d", &u, &x, &y);
a[u] = x;
b[u] = y;
}
SegT::n = d;
dfs_res(1);
printf("%lld", SegT::mx[rt[1]]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 6124kb
input:
10 9 10 1 1 2 2 3 1 3 8 3 5 4 1 9 4 1 6 8 1 3 1 1 4 9 1 10 1 1 2 6 1 8 7 1 7 9 1
output:
6
result:
wrong answer expected '7', found '6'
Subtask #2:
score: 3
Accepted
Test #10:
score: 3
Accepted
time: 51ms
memory: 18944kb
input:
100000 25000 100000 1 1 2 1 2 1 5 8 8 2 5 2 2 3 1 2 11 10 18 2 9 9 9 8 1 19 18 22 20 17 20 13 30 5 9 8 13 2 19 26 14 31 23 22 2 21 8 1 22 9 50 19 49 42 47 19 21 57 9 52 41 39 10 14 60 56 34 17 18 22 53 5 34 64 29 72 33 11 9 67 58 10 58 70 57 26 65 10 15 64 67 20 26 13 51 81 11 78 40 53 70 33 34 92 7...
output:
12471468294549
result:
ok answer is '12471468294549'
Test #11:
score: 0
Accepted
time: 46ms
memory: 20768kb
input:
100000 20000 100000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 9...
output:
10044081452141
result:
ok answer is '10044081452141'
Test #12:
score: 0
Accepted
time: 114ms
memory: 45128kb
input:
100000 90000 100000 1 1 1 1 1 1 1 1 8 1 1 8 11 11 4 4 8 11 4 4 11 4 8 8 24 4 23 4 4 11 23 11 11 1 24 24 11 23 23 23 4 24 24 11 8 11 24 23 8 24 50 1 24 23 4 24 1 4 1 11 11 50 57 23 23 54 53 55 61 23 69 54 67 11 69 24 75 23 1 53 75 1 75 1 75 50 55 61 57 55 55 23 89 8 55 11 77 89 11 24 61 23 1 75 89 67...
output:
44983082712726
result:
ok answer is '44983082712726'
Test #13:
score: 0
Accepted
time: 139ms
memory: 45380kb
input:
100000 90000 100000 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...
output:
45049819058025
result:
ok answer is '45049819058025'
Test #14:
score: 0
Accepted
time: 163ms
memory: 46928kb
input:
100000 90000 100000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 9...
output:
44931255444152
result:
ok answer is '44931255444152'
Subtask #3:
score: 0
Wrong Answer
Test #15:
score: 11
Accepted
time: 1ms
memory: 10040kb
input:
1000 500 1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...
output:
3
result:
ok answer is '3'
Test #16:
score: -11
Wrong Answer
time: 3ms
memory: 10076kb
input:
1000 500 1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...
output:
4
result:
wrong answer expected '38', found '4'
Subtask #4:
score: 0
Wrong Answer
Test #21:
score: 0
Wrong Answer
time: 59ms
memory: 12560kb
input:
100000 90000 2 1 1 3 2 1 2 1 5 1 8 11 9 1 8 12 7 1 2 7 6 12 9 16 18 13 10 23 27 26 17 23 10 24 11 21 13 30 1 11 6 13 8 30 15 17 34 39 41 32 29 27 17 21 12 26 33 10 50 29 17 46 33 21 28 47 26 3 67 38 5 10 45 61 70 59 17 46 40 20 58 67 68 15 62 71 71 57 32 81 18 66 7 14 51 67 92 86 38 88 60 45 54 5 59...
output:
36650979037247
result:
wrong answer expected '38521956905095', found '36650979037247'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Wrong Answer
Test #31:
score: 0
Wrong Answer
time: 1ms
memory: 6980kb
input:
20000 800 60000 1 1 1 2 3 1 7 8 6 1 7 6 1 7 14 16 11 13 14 3 11 11 4 2 5 24 20 24 16 30 15 3 24 31 12 7 2 29 14 25 39 23 16 33 32 33 34 9 13 37 33 23 15 21 28 39 51 19 6 50 54 55 8 40 3 7 34 19 28 15 61 18 22 28 38 15 47 37 42 73 38 61 10 7 30 58 41 43 69 89 62 84 30 68 92 84 43 59 44 75 8 100 83 18...
output:
375093435838
result:
wrong answer expected '386917987664', found '375093435838'
Subtask #7:
score: 0
Skipped
Dependency #3:
0%
Subtask #8:
score: 0
Skipped
Dependency #1:
0%