oj.uz

답안 #1045449

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1045449 2024-08-06T01:12:40 Z RauPro Mergers (JOI19_mergers) PyPy 3
34 / 100
 521 ms 262144 KB 
import sys
from collections import defaultdict
from sys import setrecursionlimit, stdin, stdout

setrecursionlimit(1000000)
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, a):
        acopy = a
        while a != self.parent[a]:
            a = self.parent[a]
        while acopy != a:
            self.parent[acopy], acopy = a, self.parent[acopy]
        return a

    def merge(self, a, b):
        self.parent[self.find(b)] = self.find(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

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 18740 KB Output is correct
2 Correct 40 ms 18740 KB Output is correct
3 Correct 39 ms 18740 KB Output is correct
4 Correct 27 ms 18568 KB Output is correct
5 Correct 27 ms 18740 KB Output is correct
6 Correct 31 ms 18740 KB Output is correct
7 Correct 26 ms 18740 KB Output is correct
8 Correct 30 ms 18856 KB Output is correct
9 Correct 27 ms 18748 KB Output is correct
10 Correct 27 ms 18684 KB Output is correct
11 Correct 32 ms 18740 KB Output is correct
12 Correct 32 ms 18840 KB Output is correct
13 Correct 27 ms 18724 KB Output is correct
14 Correct 29 ms 18748 KB Output is correct
15 Correct 30 ms 18692 KB Output is correct
16 Correct 28 ms 18740 KB Output is correct
17 Correct 30 ms 18748 KB Output is correct
18 Correct 32 ms 18784 KB Output is correct
19 Correct 29 ms 18740 KB Output is correct
20 Correct 28 ms 18748 KB Output is correct
21 Correct 31 ms 18716 KB Output is correct
22 Correct 33 ms 18772 KB Output is correct
23 Correct 30 ms 18748 KB Output is correct
24 Correct 29 ms 18792 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 18740 KB Output is correct
2 Correct 40 ms 18740 KB Output is correct
3 Correct 39 ms 18740 KB Output is correct
4 Correct 27 ms 18568 KB Output is correct
5 Correct 27 ms 18740 KB Output is correct
6 Correct 31 ms 18740 KB Output is correct
7 Correct 26 ms 18740 KB Output is correct
8 Correct 30 ms 18856 KB Output is correct
9 Correct 27 ms 18748 KB Output is correct
10 Correct 27 ms 18684 KB Output is correct
11 Correct 32 ms 18740 KB Output is correct
12 Correct 32 ms 18840 KB Output is correct
13 Correct 27 ms 18724 KB Output is correct
14 Correct 29 ms 18748 KB Output is correct
15 Correct 30 ms 18692 KB Output is correct
16 Correct 28 ms 18740 KB Output is correct
17 Correct 30 ms 18748 KB Output is correct
18 Correct 32 ms 18784 KB Output is correct
19 Correct 29 ms 18740 KB Output is correct
20 Correct 28 ms 18748 KB Output is correct
21 Correct 31 ms 18716 KB Output is correct
22 Correct 33 ms 18772 KB Output is correct
23 Correct 30 ms 18748 KB Output is correct
24 Correct 29 ms 18792 KB Output is correct
25 Correct 29 ms 18748 KB Output is correct
26 Correct 138 ms 27172 KB Output is correct
27 Correct 136 ms 29476 KB Output is correct
28 Correct 117 ms 28708 KB Output is correct
29 Correct 98 ms 26404 KB Output is correct
30 Correct 143 ms 27684 KB Output is correct
31 Correct 31 ms 18740 KB Output is correct
32 Correct 129 ms 49444 KB Output is correct
33 Correct 30 ms 18740 KB Output is correct
34 Correct 98 ms 26660 KB Output is correct
35 Correct 121 ms 27172 KB Output is correct
36 Correct 122 ms 27432 KB Output is correct
37 Correct 139 ms 27172 KB Output is correct
38 Correct 38 ms 18748 KB Output is correct
39 Correct 132 ms 27424 KB Output is correct
40 Correct 117 ms 27424 KB Output is correct
41 Correct 121 ms 27168 KB Output is correct
42 Correct 106 ms 26916 KB Output is correct
43 Correct 106 ms 29988 KB Output is correct
44 Correct 31 ms 18748 KB Output is correct
45 Correct 113 ms 34680 KB Output is correct
46 Correct 117 ms 27172 KB Output is correct
47 Correct 32 ms 18748 KB Output is correct
48 Correct 128 ms 26912 KB Output is correct
49 Correct 96 ms 26656 KB Output is correct
50 Correct 134 ms 49700 KB Output is correct
51 Correct 144 ms 26912 KB Output is correct
52 Correct 110 ms 26916 KB Output is correct
53 Correct 113 ms 26888 KB Output is correct
54 Correct 116 ms 27120 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 18740 KB Output is correct
2 Correct 40 ms 18740 KB Output is correct
3 Correct 39 ms 18740 KB Output is correct
4 Correct 27 ms 18568 KB Output is correct
5 Correct 27 ms 18740 KB Output is correct
6 Correct 31 ms 18740 KB Output is correct
7 Correct 26 ms 18740 KB Output is correct
8 Correct 30 ms 18856 KB Output is correct
9 Correct 27 ms 18748 KB Output is correct
10 Correct 27 ms 18684 KB Output is correct
11 Correct 32 ms 18740 KB Output is correct
12 Correct 32 ms 18840 KB Output is correct
13 Correct 27 ms 18724 KB Output is correct
14 Correct 29 ms 18748 KB Output is correct
15 Correct 30 ms 18692 KB Output is correct
16 Correct 28 ms 18740 KB Output is correct
17 Correct 30 ms 18748 KB Output is correct
18 Correct 32 ms 18784 KB Output is correct
19 Correct 29 ms 18740 KB Output is correct
20 Correct 28 ms 18748 KB Output is correct
21 Correct 31 ms 18716 KB Output is correct
22 Correct 33 ms 18772 KB Output is correct
23 Correct 30 ms 18748 KB Output is correct
24 Correct 29 ms 18792 KB Output is correct
25 Correct 31 ms 18732 KB Output is correct
26 Correct 371 ms 49948 KB Output is correct
27 Correct 424 ms 52004 KB Output is correct
28 Correct 114 ms 29476 KB Output is correct
29 Correct 30 ms 18716 KB Output is correct
30 Correct 30 ms 18740 KB Output is correct
31 Correct 420 ms 51492 KB Output is correct
32 Correct 99 ms 26660 KB Output is correct
33 Runtime error 397 ms 262144 KB Execution killed with signal 9
34 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 352 ms 49700 KB Output is correct
2 Correct 346 ms 50980 KB Output is correct
3 Correct 128 ms 26908 KB Output is correct
4 Correct 115 ms 29476 KB Output is correct
5 Correct 28 ms 18740 KB Output is correct
6 Correct 29 ms 18744 KB Output is correct
7 Correct 97 ms 26792 KB Output is correct
8 Correct 521 ms 61476 KB Output is correct
9 Correct 127 ms 27172 KB Output is correct
10 Correct 454 ms 51744 KB Output is correct
11 Correct 32 ms 18800 KB Output is correct
12 Correct 449 ms 60180 KB Output is correct
13 Correct 511 ms 62752 KB Output is correct
14 Correct 334 ms 49344 KB Output is correct
15 Correct 371 ms 49700 KB Output is correct
16 Correct 114 ms 26912 KB Output is correct
17 Correct 42 ms 18896 KB Output is correct
18 Correct 434 ms 52000 KB Output is correct
19 Runtime error 468 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 18740 KB Output is correct
2 Correct 40 ms 18740 KB Output is correct
3 Correct 39 ms 18740 KB Output is correct
4 Correct 27 ms 18568 KB Output is correct
5 Correct 27 ms 18740 KB Output is correct
6 Correct 31 ms 18740 KB Output is correct
7 Correct 26 ms 18740 KB Output is correct
8 Correct 30 ms 18856 KB Output is correct
9 Correct 27 ms 18748 KB Output is correct
10 Correct 27 ms 18684 KB Output is correct
11 Correct 32 ms 18740 KB Output is correct
12 Correct 32 ms 18840 KB Output is correct
13 Correct 27 ms 18724 KB Output is correct
14 Correct 29 ms 18748 KB Output is correct
15 Correct 30 ms 18692 KB Output is correct
16 Correct 28 ms 18740 KB Output is correct
17 Correct 30 ms 18748 KB Output is correct
18 Correct 32 ms 18784 KB Output is correct
19 Correct 29 ms 18740 KB Output is correct
20 Correct 28 ms 18748 KB Output is correct
21 Correct 31 ms 18716 KB Output is correct
22 Correct 33 ms 18772 KB Output is correct
23 Correct 30 ms 18748 KB Output is correct
24 Correct 29 ms 18792 KB Output is correct
25 Correct 29 ms 18748 KB Output is correct
26 Correct 138 ms 27172 KB Output is correct
27 Correct 136 ms 29476 KB Output is correct
28 Correct 117 ms 28708 KB Output is correct
29 Correct 98 ms 26404 KB Output is correct
30 Correct 143 ms 27684 KB Output is correct
31 Correct 31 ms 18740 KB Output is correct
32 Correct 129 ms 49444 KB Output is correct
33 Correct 30 ms 18740 KB Output is correct
34 Correct 98 ms 26660 KB Output is correct
35 Correct 121 ms 27172 KB Output is correct
36 Correct 122 ms 27432 KB Output is correct
37 Correct 139 ms 27172 KB Output is correct
38 Correct 38 ms 18748 KB Output is correct
39 Correct 132 ms 27424 KB Output is correct
40 Correct 117 ms 27424 KB Output is correct
41 Correct 121 ms 27168 KB Output is correct
42 Correct 106 ms 26916 KB Output is correct
43 Correct 106 ms 29988 KB Output is correct
44 Correct 31 ms 18748 KB Output is correct
45 Correct 113 ms 34680 KB Output is correct
46 Correct 117 ms 27172 KB Output is correct
47 Correct 32 ms 18748 KB Output is correct
48 Correct 128 ms 26912 KB Output is correct
49 Correct 96 ms 26656 KB Output is correct
50 Correct 134 ms 49700 KB Output is correct
51 Correct 144 ms 26912 KB Output is correct
52 Correct 110 ms 26916 KB Output is correct
53 Correct 113 ms 26888 KB Output is correct
54 Correct 116 ms 27120 KB Output is correct
55 Correct 31 ms 18732 KB Output is correct
56 Correct 371 ms 49948 KB Output is correct
57 Correct 424 ms 52004 KB Output is correct
58 Correct 114 ms 29476 KB Output is correct
59 Correct 30 ms 18716 KB Output is correct
60 Correct 30 ms 18740 KB Output is correct
61 Correct 420 ms 51492 KB Output is correct
62 Correct 99 ms 26660 KB Output is correct
63 Runtime error 397 ms 262144 KB Execution killed with signal 9
64 Halted 0 ms 0 KB -