QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#401225#946. Magic Treesichengzhou0 1137ms158648kbC++142.6kb2024-04-28 09:16:352024-04-28 09:16:36

Judging History

你现在查看的是最新测评结果

  • [2024-04-28 09:16:36]
  • 评测
  • 测评结果:0
  • 用时:1137ms
  • 内存:158648kb
  • [2024-04-28 09:16:35]
  • 提交

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 val[N];
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]);
        val[++val[0]]=d[x];
    }
    sort(val+1,val+val[0]+1);
    for(int i=1;i<=n;i++)
    {
        if(w[i])
        {
            d[i]=lower_bound(val+1,val+val[0]+1,d[i])-val;
        }
    }
    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: 0
Wrong Answer

Test #1:

score: 6
Accepted
time: 1ms
memory: 8060kb

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: 0
Accepted
time: 1ms
memory: 5928kb

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: 0
Accepted
time: 1ms
memory: 5980kb

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
Wrong Answer
time: 1ms
memory: 5952kb

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:

6

result:

wrong answer expected '14', found '6'

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: 3ms
memory: 12224kb

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: 0
Accepted
time: 0ms
memory: 14180kb

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: 0
Accepted
time: 0ms
memory: 12124kb

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: -11
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: 0
Runtime Error

Test #21:

score: 0
Runtime Error

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:


result:


Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Wrong Answer

Test #31:

score: 0
Wrong Answer
time: 1137ms
memory: 158648kb

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:

9192027148570393450

result:

wrong answer expected '386917987664', found '9192027148570393450'

Subtask #7:

score: 0
Skipped

Dependency #3:

0%

Subtask #8:

score: 0
Skipped

Dependency #1:

0%