Submission #1045440

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1045440	2024-08-06T01:05:56 Z	RauPro	Mergers (JOI19_mergers)	PyPy 3	34 / 100	668 ms	262144 KB

mergers

import sys
from collections import defaultdict
from sys import setrecursionlimit, stdin, stdout

setrecursionlimit(200000)
class DSU:
    def __init__(self, n):
        self.par = list(range(n))

    def find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

    def merge(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a != b:
            self.par[b] = a


def setup(v, parent):
    for p in graf[v]:
        if p == parent:
            continue
        depth[p] = depth[v] + 1
        up[p] = v
        setup(p, v)


def merge(a, b):
    a = dsu.find(a)
    b = dsu.find(b)
    while a != b:
        if depth[a] < depth[b]:
            a, b = b, a
        dsu.merge(up[a], a)
        a = dsu.find(up[a])



n, k = map(int, input().split())

graf = [[] for i in range(n+1)]
dsu = DSU(n)
up = [0] * n
depth = [0] * n

for _ in range(n - 1):
    a, b = map(int, input().split())
    a-=1
    b-=1
    graf[a].append(b)
    graf[b].append(a)

setup(0, -1)

groups = [[] for i in range(n+1)]
for i in range(n):
    a = int(input()) - 1
    groups[a].append(i)

for group in groups:
    for j in range(1, len(group)):
        merge(group[0], group[j])

sol = 0
deg = [0] * n
for i in range(n):
    for p in graf[i]:
        if dsu.find(i) != dsu.find(p):
            if deg[dsu.find(i)] == 0:
                sol += 1
            if deg[dsu.find(i)] == 1:
                sol -= 1
            deg[dsu.find(i)] += 1

print((sol + 1) // 2)

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	18748 KB	Output is correct
2	Correct	31 ms	18812 KB	Output is correct
3	Correct	29 ms	18700 KB	Output is correct
4	Correct	29 ms	18748 KB	Output is correct
5	Correct	29 ms	18748 KB	Output is correct
6	Correct	31 ms	18748 KB	Output is correct
7	Correct	27 ms	18748 KB	Output is correct
8	Correct	30 ms	19308 KB	Output is correct
9	Correct	26 ms	18748 KB	Output is correct
10	Correct	27 ms	18636 KB	Output is correct
11	Correct	30 ms	18748 KB	Output is correct
12	Correct	29 ms	18736 KB	Output is correct
13	Correct	29 ms	18748 KB	Output is correct
14	Correct	30 ms	18892 KB	Output is correct
15	Correct	35 ms	18748 KB	Output is correct
16	Correct	27 ms	18740 KB	Output is correct
17	Correct	28 ms	18740 KB	Output is correct
18	Correct	30 ms	18748 KB	Output is correct
19	Correct	25 ms	18764 KB	Output is correct
20	Correct	27 ms	18748 KB	Output is correct
21	Correct	30 ms	18724 KB	Output is correct
22	Correct	31 ms	18748 KB	Output is correct
23	Correct	27 ms	18740 KB	Output is correct
24	Correct	27 ms	18696 KB	Output is correct

Subtask #2
24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	18748 KB	Output is correct
2	Correct	31 ms	18812 KB	Output is correct
3	Correct	29 ms	18700 KB	Output is correct
4	Correct	29 ms	18748 KB	Output is correct
5	Correct	29 ms	18748 KB	Output is correct
6	Correct	31 ms	18748 KB	Output is correct
7	Correct	27 ms	18748 KB	Output is correct
8	Correct	30 ms	19308 KB	Output is correct
9	Correct	26 ms	18748 KB	Output is correct
10	Correct	27 ms	18636 KB	Output is correct
11	Correct	30 ms	18748 KB	Output is correct
12	Correct	29 ms	18736 KB	Output is correct
13	Correct	29 ms	18748 KB	Output is correct
14	Correct	30 ms	18892 KB	Output is correct
15	Correct	35 ms	18748 KB	Output is correct
16	Correct	27 ms	18740 KB	Output is correct
17	Correct	28 ms	18740 KB	Output is correct
18	Correct	30 ms	18748 KB	Output is correct
19	Correct	25 ms	18764 KB	Output is correct
20	Correct	27 ms	18748 KB	Output is correct
21	Correct	30 ms	18724 KB	Output is correct
22	Correct	31 ms	18748 KB	Output is correct
23	Correct	27 ms	18740 KB	Output is correct
24	Correct	27 ms	18696 KB	Output is correct
25	Correct	29 ms	18748 KB	Output is correct
26	Correct	135 ms	26924 KB	Output is correct
27	Correct	138 ms	30608 KB	Output is correct
28	Correct	131 ms	30752 KB	Output is correct
29	Correct	113 ms	26400 KB	Output is correct
30	Correct	132 ms	27172 KB	Output is correct
31	Correct	29 ms	18740 KB	Output is correct
32	Correct	124 ms	51492 KB	Output is correct
33	Correct	31 ms	18676 KB	Output is correct
34	Correct	93 ms	26660 KB	Output is correct
35	Correct	98 ms	27168 KB	Output is correct
36	Correct	116 ms	27148 KB	Output is correct
37	Correct	126 ms	27036 KB	Output is correct
38	Correct	30 ms	18748 KB	Output is correct
39	Correct	126 ms	27684 KB	Output is correct
40	Correct	124 ms	27684 KB	Output is correct
41	Correct	123 ms	26660 KB	Output is correct
42	Correct	109 ms	27168 KB	Output is correct
43	Correct	106 ms	30240 KB	Output is correct
44	Correct	31 ms	18748 KB	Output is correct
45	Correct	121 ms	36452 KB	Output is correct
46	Correct	117 ms	26912 KB	Output is correct
47	Correct	31 ms	18708 KB	Output is correct
48	Correct	127 ms	26916 KB	Output is correct
49	Correct	92 ms	26400 KB	Output is correct
50	Correct	114 ms	49948 KB	Output is correct
51	Correct	124 ms	26916 KB	Output is correct
52	Correct	105 ms	26748 KB	Output is correct
53	Correct	113 ms	27168 KB	Output is correct
54	Correct	122 ms	27428 KB	Output is correct

Subtask #3
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	18748 KB	Output is correct
2	Correct	31 ms	18812 KB	Output is correct
3	Correct	29 ms	18700 KB	Output is correct
4	Correct	29 ms	18748 KB	Output is correct
5	Correct	29 ms	18748 KB	Output is correct
6	Correct	31 ms	18748 KB	Output is correct
7	Correct	27 ms	18748 KB	Output is correct
8	Correct	30 ms	19308 KB	Output is correct
9	Correct	26 ms	18748 KB	Output is correct
10	Correct	27 ms	18636 KB	Output is correct
11	Correct	30 ms	18748 KB	Output is correct
12	Correct	29 ms	18736 KB	Output is correct
13	Correct	29 ms	18748 KB	Output is correct
14	Correct	30 ms	18892 KB	Output is correct
15	Correct	35 ms	18748 KB	Output is correct
16	Correct	27 ms	18740 KB	Output is correct
17	Correct	28 ms	18740 KB	Output is correct
18	Correct	30 ms	18748 KB	Output is correct
19	Correct	25 ms	18764 KB	Output is correct
20	Correct	27 ms	18748 KB	Output is correct
21	Correct	30 ms	18724 KB	Output is correct
22	Correct	31 ms	18748 KB	Output is correct
23	Correct	27 ms	18740 KB	Output is correct
24	Correct	27 ms	18696 KB	Output is correct
25	Correct	29 ms	18748 KB	Output is correct
26	Correct	331 ms	49136 KB	Output is correct
27	Correct	493 ms	59424 KB	Output is correct
28	Correct	121 ms	31496 KB	Output is correct
29	Correct	30 ms	18784 KB	Output is correct
30	Correct	29 ms	18748 KB	Output is correct
31	Correct	471 ms	59684 KB	Output is correct
32	Correct	94 ms	26568 KB	Output is correct
33	Runtime error	409 ms	262144 KB	Execution killed with signal 9
34	Halted	0 ms	0 KB	-

Subtask #4
0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	321 ms	49156 KB	Output is correct
2	Correct	300 ms	50836 KB	Output is correct
3	Correct	139 ms	26912 KB	Output is correct
4	Correct	127 ms	31560 KB	Output is correct
5	Correct	29 ms	18740 KB	Output is correct
6	Correct	29 ms	18748 KB	Output is correct
7	Correct	93 ms	26676 KB	Output is correct
8	Correct	605 ms	66568 KB	Output is correct
9	Correct	119 ms	27124 KB	Output is correct
10	Correct	512 ms	65000 KB	Output is correct
11	Correct	30 ms	18748 KB	Output is correct
12	Correct	422 ms	53964 KB	Output is correct
13	Correct	668 ms	69368 KB	Output is correct
14	Correct	321 ms	49440 KB	Output is correct
15	Correct	335 ms	49696 KB	Output is correct
16	Correct	107 ms	27156 KB	Output is correct
17	Correct	30 ms	18748 KB	Output is correct
18	Correct	338 ms	51704 KB	Output is correct
19	Runtime error	437 ms	262144 KB	Execution killed with signal 9
20	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	18748 KB	Output is correct
2	Correct	31 ms	18812 KB	Output is correct
3	Correct	29 ms	18700 KB	Output is correct
4	Correct	29 ms	18748 KB	Output is correct
5	Correct	29 ms	18748 KB	Output is correct
6	Correct	31 ms	18748 KB	Output is correct
7	Correct	27 ms	18748 KB	Output is correct
8	Correct	30 ms	19308 KB	Output is correct
9	Correct	26 ms	18748 KB	Output is correct
10	Correct	27 ms	18636 KB	Output is correct
11	Correct	30 ms	18748 KB	Output is correct
12	Correct	29 ms	18736 KB	Output is correct
13	Correct	29 ms	18748 KB	Output is correct
14	Correct	30 ms	18892 KB	Output is correct
15	Correct	35 ms	18748 KB	Output is correct
16	Correct	27 ms	18740 KB	Output is correct
17	Correct	28 ms	18740 KB	Output is correct
18	Correct	30 ms	18748 KB	Output is correct
19	Correct	25 ms	18764 KB	Output is correct
20	Correct	27 ms	18748 KB	Output is correct
21	Correct	30 ms	18724 KB	Output is correct
22	Correct	31 ms	18748 KB	Output is correct
23	Correct	27 ms	18740 KB	Output is correct
24	Correct	27 ms	18696 KB	Output is correct
25	Correct	29 ms	18748 KB	Output is correct
26	Correct	135 ms	26924 KB	Output is correct
27	Correct	138 ms	30608 KB	Output is correct
28	Correct	131 ms	30752 KB	Output is correct
29	Correct	113 ms	26400 KB	Output is correct
30	Correct	132 ms	27172 KB	Output is correct
31	Correct	29 ms	18740 KB	Output is correct
32	Correct	124 ms	51492 KB	Output is correct
33	Correct	31 ms	18676 KB	Output is correct
34	Correct	93 ms	26660 KB	Output is correct
35	Correct	98 ms	27168 KB	Output is correct
36	Correct	116 ms	27148 KB	Output is correct
37	Correct	126 ms	27036 KB	Output is correct
38	Correct	30 ms	18748 KB	Output is correct
39	Correct	126 ms	27684 KB	Output is correct
40	Correct	124 ms	27684 KB	Output is correct
41	Correct	123 ms	26660 KB	Output is correct
42	Correct	109 ms	27168 KB	Output is correct
43	Correct	106 ms	30240 KB	Output is correct
44	Correct	31 ms	18748 KB	Output is correct
45	Correct	121 ms	36452 KB	Output is correct
46	Correct	117 ms	26912 KB	Output is correct
47	Correct	31 ms	18708 KB	Output is correct
48	Correct	127 ms	26916 KB	Output is correct
49	Correct	92 ms	26400 KB	Output is correct
50	Correct	114 ms	49948 KB	Output is correct
51	Correct	124 ms	26916 KB	Output is correct
52	Correct	105 ms	26748 KB	Output is correct
53	Correct	113 ms	27168 KB	Output is correct
54	Correct	122 ms	27428 KB	Output is correct
55	Correct	29 ms	18748 KB	Output is correct
56	Correct	331 ms	49136 KB	Output is correct
57	Correct	493 ms	59424 KB	Output is correct
58	Correct	121 ms	31496 KB	Output is correct
59	Correct	30 ms	18784 KB	Output is correct
60	Correct	29 ms	18748 KB	Output is correct
61	Correct	471 ms	59684 KB	Output is correct
62	Correct	94 ms	26568 KB	Output is correct
63	Runtime error	409 ms	262144 KB	Execution killed with signal 9
64	Halted	0 ms	0 KB	-

Submission #1045440

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 24.0 / 24.0

Subtask #3 0 / 14.0

Subtask #4 0 / 22.0

Subtask #5 0 / 30.0

Subtask #1
10.0 / 10.0

Subtask #2
24.0 / 24.0

Subtask #3
0 / 14.0

Subtask #4
0 / 22.0

Subtask #5
0 / 30.0