QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#401224 | #946. Magic Tree | sichengzhou | 30.5 | 1158ms | 798744kb | C++14 | 2.4kb | 2024-04-28 09:13:39 | 2024-04-28 09:13:40 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+5,M=1e3+3;
int n,m,K,fa[N],d[N],w[N];
struct Edge{
int v,nxt;
}e[N];
int h[N],tot1;
void addEdge(int u,int v)
{
tot1++;
e[tot1].v=v;e[tot1].nxt=h[u];
h[u]=tot1;
}
LL f[N][M];
struct Seg{
int l,r;
LL val,mx,lz;
}t[N*18];
int rt[N],tot;
void update(int p)
{
t[p].val=max(t[t[p].l].val,t[t[p].r].val);
}
void pushlz(int p,LL z)
{
t[p].mx+=z;
t[p].lz+=z;
t[p].val+=z;
}
void pushmx(int p,LL z)
{
t[p].mx=max(t[p].mx,z);
t[p].val=max(t[p].val,z);
}
void lzdown(int p)
{
if(t[p].l)
{
pushlz(t[p].l,t[p].lz);
pushmx(t[p].l,t[p].mx);
}
if(t[p].r)
{
pushlz(t[p].r,t[p].lz);
pushmx(t[p].r,t[p].mx);
}
t[p].mx=0;t[p].lz=0;
}
void insert(int &p,int l,int r,int x,LL y)
{
if(p==0)
{
p=++tot;
}
if(l==r)
{
t[p].val=y;
return ;
}
int mid=l+r>>1;
if(x<=mid)
{
insert(t[p].l,l,mid,x,y);
}else{
insert(t[p].r,mid+1,r,x,y);
}
update(p);
}
void merge(int &x,int y,int l,int r)
{
if(x==0)
{
x=y;
return ;
}
if(y==0)
{
return ;
}
if(l==r)
{
t[x].val=t[x].val+t[y].val;
return ;
}
lzdown(x);
lzdown(y);
int mid=l+r>>1;
if(t[y].r==0)
{
if(t[x].r)
{
pushlz(t[x].r,t[t[y].l].val);
}
}else{
pushmx(t[y].r,t[t[y].l].val);
}
merge(t[x].l,t[y].l,l,mid);
merge(t[x].r,t[y].r,mid+1,r);
update(x);
}
void dfs(int u)
{
if(w[u])
{
f[u][d[u]]=w[u];
// insert(rt[u],1,K,d[u],w[u]);
}
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
dfs(v);
LL mx=0;
for(int j=1;j<=K;j++)
{
mx=max(mx,f[v][j]);
f[u][j]+=mx;
}
// merge(rt[u],rt[v],1,K);
}
}
int main()
{
int x;
scanf("%d%d%d",&n,&m,&K);
for(int i=2;i<=n;i++)
{
scanf("%d",&fa[i]);
addEdge(fa[i],i);
}
for(int i=1;i<=m;i++)
{
scanf("%d",&x);
scanf("%d%d",&d[x],&w[x]);
}
dfs(1);
LL mx=0;
for(int i=1;i<=K;i++)
{
mx=max(mx,f[1][i]);
}
printf("%lld\n",mx);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 6
Accepted
Test #1:
score: 6
Accepted
time: 0ms
memory: 7932kb
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:
7
result:
ok answer is '7'
Test #2:
score: 6
Accepted
time: 0ms
memory: 6020kb
input:
20 19 20 1 1 2 1 3 6 5 1 5 8 1 10 3 7 4 16 13 4 2 14 13 1 18 9 1 15 16 1 9 20 1 4 18 1 12 15 1 2 6 1 16 13 1 5 5 1 17 19 1 7 4 1 11 14 1 8 3 1 10 1 1 20 16 1 13 1 1 6 4 1 3 12 1 19 20 1
output:
12
result:
ok answer is '12'
Test #3:
score: 6
Accepted
time: 1ms
memory: 5900kb
input:
20 10 10 1 1 3 1 5 2 1 8 2 4 6 9 12 8 15 14 6 5 17 6 7 1 3 6 1 14 5 1 20 7 1 16 7 1 9 6 1 13 4 1 17 1 1 4 2 1 12 7 1
output:
9
result:
ok answer is '9'
Test #4:
score: 6
Accepted
time: 1ms
memory: 5840kb
input:
20 19 8 1 2 3 3 3 5 5 4 4 4 2 11 9 6 3 2 11 2 12 3 6 1 17 8 1 20 6 1 10 7 1 8 5 1 16 5 1 11 2 1 15 5 1 18 8 1 5 4 1 7 8 1 6 4 1 2 4 1 13 1 1 9 6 1 19 7 1 12 7 1 14 2 1 4 8 1
output:
14
result:
ok answer is '14'
Test #5:
score: 6
Accepted
time: 1ms
memory: 8036kb
input:
20 19 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2 1 1 3 3 1 4 3 1 5 4 1 6 4 1 7 6 1 8 7 1 9 9 1 10 14 1 11 14 1 12 14 1 13 15 1 14 18 1 15 19 1 16 19 1 17 19 1 18 20 1 19 20 1 20 20 1
output:
3
result:
ok answer is '3'
Test #6:
score: 6
Accepted
time: 1ms
memory: 6024kb
input:
20 19 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2 3 1 3 12 1 4 8 1 5 20 1 6 18 1 7 6 1 8 8 1 9 14 1 10 7 1 11 5 1 12 14 1 13 13 1 14 11 1 15 7 1 16 15 1 17 18 1 18 5 1 19 10 1 20 13 1
output:
8
result:
ok answer is '8'
Test #7:
score: 6
Accepted
time: 1ms
memory: 5816kb
input:
20 19 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2 20 1 3 17 1 4 15 1 5 14 1 6 9 1 7 9 1 8 7 1 9 7 1 10 6 1 11 4 1 12 4 1 13 4 1 14 3 1 15 3 1 16 2 1 17 2 1 18 2 1 19 1 1 20 1 1
output:
19
result:
ok answer is '19'
Test #8:
score: 6
Accepted
time: 0ms
memory: 5984kb
input:
20 15 20 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 14 1 7 6 1 20 3 1 3 1 1 18 7 1 10 10 1 11 3 1 12 17 1 9 14 1 8 12 1 5 12 1 13 14 1 4 11 1 15 14 1 17 5 1
output:
14
result:
ok answer is '14'
Test #9:
score: 6
Accepted
time: 1ms
memory: 6020kb
input:
20 15 20 1 2 3 4 2 6 7 5 8 5 10 12 11 11 13 16 15 18 19 2 11 1 12 15 1 15 1 1 20 12 1 13 16 1 10 6 1 4 6 1 11 19 1 18 13 1 3 14 1 7 15 1 16 11 1 9 12 1 14 3 1 5 19 1
output:
9
result:
ok answer is '9'
Subtask #2:
score: 0
Time Limit Exceeded
Test #10:
score: 0
Time Limit Exceeded
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:
result:
Subtask #3:
score: 0
Time Limit Exceeded
Test #15:
score: 11
Accepted
time: 4ms
memory: 16216kb
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
Accepted
time: 3ms
memory: 14316kb
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:
38
result:
ok answer is '38'
Test #17:
score: 11
Accepted
time: 3ms
memory: 14192kb
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:
500
result:
ok answer is '500'
Test #18:
score: 0
Time Limit Exceeded
input:
100000 99999 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:
result:
Subtask #4:
score: 12
Accepted
Test #21:
score: 12
Accepted
time: 31ms
memory: 770836kb
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:
38521956905095
result:
ok answer is '38521956905095'
Test #22:
score: 12
Accepted
time: 27ms
memory: 760672kb
input:
100000 90000 1 1 1 2 2 5 1 2 7 3 6 3 7 8 6 11 1 17 11 15 1 11 3 7 4 11 12 20 5 14 17 29 4 6 27 29 1 9 11 1 5 23 42 36 10 16 39 34 14 31 5 22 48 43 43 1 34 51 26 10 16 22 15 42 8 63 27 57 16 50 60 23 67 44 13 40 60 49 55 77 73 44 32 80 50 26 20 24 72 75 21 47 74 24 67 59 43 19 17 85 61 12 99 21 104 1...
output:
44817789931778
result:
ok answer is '44817789931778'
Test #23:
score: 12
Accepted
time: 40ms
memory: 756972kb
input:
100000 90000 2 1 2 3 2 5 5 4 7 9 8 11 10 3 12 15 10 17 16 18 3 19 20 23 24 2 22 25 10 28 27 30 31 32 33 35 34 37 36 24 39 41 42 43 44 38 20 9 45 49 50 46 52 52 30 51 53 57 58 56 59 23 31 60 64 65 66 67 61 28 69 71 72 41 73 68 75 77 12 5 76 4 78 77 51 81 83 87 7 88 86 28 91 93 90 94 96 95 98 99 100 9...
output:
27165432883093
result:
ok answer is '27165432883093'
Test #24:
score: 12
Accepted
time: 7ms
memory: 758432kb
input:
100000 90000 2 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 2 2 2...
output:
44981598598688
result:
ok answer is '44981598598688'
Test #25:
score: 12
Accepted
time: 23ms
memory: 798732kb
input:
100000 90000 2 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 ...
output:
22589648566145
result:
ok answer is '22589648566145'
Subtask #5:
score: 12.5
Accepted
Dependency #1:
100%
Accepted
Test #26:
score: 12.5
Accepted
time: 32ms
memory: 772052kb
input:
100000 90000 20 1 2 3 3 3 4 6 2 7 3 4 6 10 6 13 1 11 7 8 18 1 19 7 4 9 4 20 9 26 9 6 5 23 2 23 11 5 17 28 19 14 34 36 43 32 10 41 1 19 28 35 6 40 6 23 15 6 32 15 15 21 6 30 62 51 11 46 45 21 2 41 31 8 9 9 9 25 26 79 68 66 4 52 6 64 6 52 52 67 74 80 15 39 58 11 90 2 53 12 45 75 61 62 61 57 19 95 50 1...
output:
62571
result:
ok answer is '62571'
Test #27:
score: 12.5
Accepted
time: 23ms
memory: 771272kb
input:
100000 90000 10 1 1 1 4 2 5 5 8 2 5 4 7 7 1 7 16 1 13 18 5 13 15 6 24 10 16 20 22 25 17 23 31 22 25 29 8 4 20 24 40 26 10 26 23 10 13 12 34 41 16 9 21 51 17 50 32 54 12 35 51 4 27 48 18 43 42 49 29 30 64 29 25 58 64 73 61 45 24 78 6 26 33 34 68 44 22 83 11 73 59 13 58 3 87 3 55 72 14 37 37 5 40 3 21...
output:
63666
result:
ok answer is '63666'
Test #28:
score: 12.5
Accepted
time: 35ms
memory: 749724kb
input:
100000 90000 20 1 2 2 3 5 3 4 4 6 9 10 12 13 14 11 16 3 17 19 20 21 15 19 23 22 25 16 27 26 27 31 32 30 33 35 36 34 37 38 40 41 42 39 44 43 45 46 47 49 22 32 50 48 20 53 54 57 56 59 58 61 62 63 25 60 66 67 64 68 69 71 72 19 46 70 76 77 73 79 2 80 78 83 82 35 85 87 84 88 89 91 90 73 93 92 95 96 17 57...
output:
21768
result:
ok answer is '21768'
Test #29:
score: 12.5
Accepted
time: 28ms
memory: 751980kb
input:
100000 90000 20 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 2 2 ...
output:
89999
result:
ok answer is '89999'
Test #30:
score: 12.5
Accepted
time: 24ms
memory: 798744kb
input:
100000 90000 20 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...
output:
5018
result:
ok answer is '5018'
Subtask #6:
score: 0
Wrong Answer
Test #31:
score: 0
Wrong Answer
time: 1158ms
memory: 158456kb
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:
9170020770967443653
result:
wrong answer expected '386917987664', found '9170020770967443653'
Subtask #7:
score: 0
Skipped
Dependency #3:
0%
Subtask #8:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%