oj.uz

Submission #1048130

# Submission time Handle Problem Language Result Execution time Memory
1048130 2024-08-08T00:00:17 Z RauPro Mergers (JOI19_mergers) PyPy 3
100 / 100
 1567 ms 248796 KB 
import os
import sys
from collections import *
from heapq import *
from math import gcd, floor, ceil, sqrt
from copy import deepcopy
from itertools import permutations, combinations, product
from bisect import bisect_left, bisect_right
from functools import lru_cache, reduce
import operator
from random import getrandbits

# Para mejorar el rendimiento de la entrada/salida
input = lambda: sys.stdin.readline().strip()
flush = lambda: sys.stdout.flush()
print = lambda *args, **kwargs: sys.stdout.write(' '.join(map(str, args)) + kwargs.get("end", "\n")) and flush()

# Optimización de la recursión para Python
sys.setrecursionlimit(100000)


# Funciones para lectura de múltiples tipos de datos
def ints(): return map(int, input().split())
def strs(): return input().split()
def chars(): return list(input().strip())
def mat(n): return [list(ints()) for _ in range(n)]  # Matriz de n x m donde m es el número de enteros en una línea


# Constantes útiles
INF = float('inf')
MOD = 1000000007  # Modulo por defecto, cambiar si se necesita otro
abcd = "abcdefghijklmnopqrstuvwxyz"

# Algunas funciones útiles
def add(x, y, mod=MOD): return (x + y) % mod
def sub(x, y, mod=MOD): return (x - y) % mod
def mul(x, y, mod=MOD): return (x * y) % mod

# Inverso multiplicativo de a modulo m (cuando m es primo)
def invmod(a, mod=MOD): return powmod(a, mod - 2, mod)

def lcm(a, b): return a * b // gcd(a, b)

RANDOM = getrandbits(32)

class Wrapper(int):
    def __init__(self, x):
        int.__init__(x)
    def __hash__(self):
        return super(Wrapper, self).__hash__() ^ RANDOM


depth = []
parent = []
visited = []
AL = []
uf = None


class UF:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.num_sets = 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 union(self, a, b):
        a, b = self.find(a), self.find(b)
        self.num_sets -= 1
        self.parent[b] = a
        self.size[a] += self.size[b]

    def set_size(self, a):
        return self.size[self.find(a)]

    def __len__(self):
        return self.num_sets


# Tree compression from vertex a to b
def path_compression(a, b):
    a = uf.find(a)
    b = uf.find(b)
    while a != b:
        if depth[a] < depth[b]:
            b, a = a, b
        uf.union(parent[a], a)
        a = uf.find(parent[a])


def dfs(u, lvl, p):
    global AL, visited, parent, depth, uf
    stack = [(u, lvl, p)]
    while stack:
        u, lvl, p = stack.pop()
        for v in AL[u]:
            if not visited[v]:
                stack.append((v, lvl+1, u))
        visited[u] = True
        depth[u] = lvl
        parent[u] = p
def main():
    global AL, visited, parent, depth, uf
    n, m = ints()
    AL = [[] for i in range(n+1)]
    for i in range(n-1):
        u,v = ints()
        AL[u].append(v)
        AL[v].append(u)
    tree_groups = [[] for i in range(n+1)]
    for i in range(n):
        g = int(input())
        tree_groups[g].append(i+1)

    #print(tree_groups)
    visited = [False] * (n+1)
    parent = [0] * (n+1)
    depth = [0] * (n + 1)
    dfs(1, 0, 1)

    #print(depth, parent)
    uf = UF(n+1)
    for group in tree_groups:
        for i in range(1, len(group)):
            path_compression(group[0], group[i])

    degree = [0] * (n+1)
    for u in range(1, n+1):
        for v in AL[u]:
            if uf.find(u) != uf.find(v):
                degree[uf.find(u)] += 1
    ans = sum(1 for it in degree if it == 1)
    print((ans + 1) // 2)




if __name__ == "__main__":
    main()

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 23788 KB Output is correct
2 Correct 69 ms 23856 KB Output is correct
3 Correct 72 ms 23956 KB Output is correct
4 Correct 65 ms 23852 KB Output is correct
5 Correct 66 ms 23836 KB Output is correct
6 Correct 68 ms 24060 KB Output is correct
7 Correct 67 ms 23856 KB Output is correct
8 Correct 73 ms 24064 KB Output is correct
9 Correct 72 ms 23852 KB Output is correct
10 Correct 80 ms 23852 KB Output is correct
11 Correct 69 ms 23856 KB Output is correct
12 Correct 68 ms 23844 KB Output is correct
13 Correct 70 ms 24096 KB Output is correct
14 Correct 67 ms 23868 KB Output is correct
15 Correct 68 ms 23856 KB Output is correct
16 Correct 69 ms 23964 KB Output is correct
17 Correct 65 ms 23856 KB Output is correct
18 Correct 92 ms 23856 KB Output is correct
19 Correct 69 ms 23856 KB Output is correct
20 Correct 67 ms 23832 KB Output is correct
21 Correct 67 ms 23936 KB Output is correct
22 Correct 69 ms 23984 KB Output is correct
23 Correct 66 ms 23852 KB Output is correct
24 Correct 66 ms 23856 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 23788 KB Output is correct
2 Correct 69 ms 23856 KB Output is correct
3 Correct 72 ms 23956 KB Output is correct
4 Correct 65 ms 23852 KB Output is correct
5 Correct 66 ms 23836 KB Output is correct
6 Correct 68 ms 24060 KB Output is correct
7 Correct 67 ms 23856 KB Output is correct
8 Correct 73 ms 24064 KB Output is correct
9 Correct 72 ms 23852 KB Output is correct
10 Correct 80 ms 23852 KB Output is correct
11 Correct 69 ms 23856 KB Output is correct
12 Correct 68 ms 23844 KB Output is correct
13 Correct 70 ms 24096 KB Output is correct
14 Correct 67 ms 23868 KB Output is correct
15 Correct 68 ms 23856 KB Output is correct
16 Correct 69 ms 23964 KB Output is correct
17 Correct 65 ms 23856 KB Output is correct
18 Correct 92 ms 23856 KB Output is correct
19 Correct 69 ms 23856 KB Output is correct
20 Correct 67 ms 23832 KB Output is correct
21 Correct 67 ms 23936 KB Output is correct
22 Correct 69 ms 23984 KB Output is correct
23 Correct 66 ms 23852 KB Output is correct
24 Correct 66 ms 23856 KB Output is correct
25 Correct 71 ms 23812 KB Output is correct
26 Correct 135 ms 29144 KB Output is correct
27 Correct 105 ms 27416 KB Output is correct
28 Correct 120 ms 27408 KB Output is correct
29 Correct 98 ms 27148 KB Output is correct
30 Correct 118 ms 28212 KB Output is correct
31 Correct 70 ms 23852 KB Output is correct
32 Correct 105 ms 28184 KB Output is correct
33 Correct 73 ms 24112 KB Output is correct
34 Correct 102 ms 27160 KB Output is correct
35 Correct 100 ms 27156 KB Output is correct
36 Correct 126 ms 29464 KB Output is correct
37 Correct 124 ms 28948 KB Output is correct
38 Correct 68 ms 23856 KB Output is correct
39 Correct 126 ms 28696 KB Output is correct
40 Correct 116 ms 28436 KB Output is correct
41 Correct 132 ms 29440 KB Output is correct
42 Correct 120 ms 28752 KB Output is correct
43 Correct 108 ms 27160 KB Output is correct
44 Correct 69 ms 23852 KB Output is correct
45 Correct 128 ms 27160 KB Output is correct
46 Correct 127 ms 28176 KB Output is correct
47 Correct 66 ms 24076 KB Output is correct
48 Correct 134 ms 29976 KB Output is correct
49 Correct 93 ms 27668 KB Output is correct
50 Correct 100 ms 27140 KB Output is correct
51 Correct 125 ms 28876 KB Output is correct
52 Correct 112 ms 28192 KB Output is correct
53 Correct 114 ms 28696 KB Output is correct
54 Correct 113 ms 28184 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 23788 KB Output is correct
2 Correct 69 ms 23856 KB Output is correct
3 Correct 72 ms 23956 KB Output is correct
4 Correct 65 ms 23852 KB Output is correct
5 Correct 66 ms 23836 KB Output is correct
6 Correct 68 ms 24060 KB Output is correct
7 Correct 67 ms 23856 KB Output is correct
8 Correct 73 ms 24064 KB Output is correct
9 Correct 72 ms 23852 KB Output is correct
10 Correct 80 ms 23852 KB Output is correct
11 Correct 69 ms 23856 KB Output is correct
12 Correct 68 ms 23844 KB Output is correct
13 Correct 70 ms 24096 KB Output is correct
14 Correct 67 ms 23868 KB Output is correct
15 Correct 68 ms 23856 KB Output is correct
16 Correct 69 ms 23964 KB Output is correct
17 Correct 65 ms 23856 KB Output is correct
18 Correct 92 ms 23856 KB Output is correct
19 Correct 69 ms 23856 KB Output is correct
20 Correct 67 ms 23832 KB Output is correct
21 Correct 67 ms 23936 KB Output is correct
22 Correct 69 ms 23984 KB Output is correct
23 Correct 66 ms 23852 KB Output is correct
24 Correct 66 ms 23856 KB Output is correct
25 Correct 66 ms 23960 KB Output is correct
26 Correct 276 ms 62996 KB Output is correct
27 Correct 284 ms 51732 KB Output is correct
28 Correct 104 ms 27412 KB Output is correct
29 Correct 67 ms 23904 KB Output is correct
30 Correct 65 ms 23856 KB Output is correct
31 Correct 299 ms 53260 KB Output is correct
32 Correct 101 ms 27156 KB Output is correct
33 Correct 283 ms 48404 KB Output is correct
34 Correct 296 ms 51436 KB Output is correct
35 Correct 125 ms 29452 KB Output is correct
36 Correct 256 ms 48640 KB Output is correct
37 Correct 117 ms 27672 KB Output is correct
38 Correct 126 ms 29208 KB Output is correct
39 Correct 269 ms 58208 KB Output is correct
40 Correct 105 ms 27156 KB Output is correct
41 Correct 286 ms 52776 KB Output is correct
42 Correct 244 ms 47900 KB Output is correct
43 Correct 81 ms 24060 KB Output is correct
44 Correct 260 ms 47780 KB Output is correct
45 Correct 268 ms 52248 KB Output is correct
46 Correct 110 ms 28184 KB Output is correct
47 Correct 117 ms 28180 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 63208 KB Output is correct
2 Correct 250 ms 66124 KB Output is correct
3 Correct 122 ms 29032 KB Output is correct
4 Correct 106 ms 27416 KB Output is correct
5 Correct 82 ms 23792 KB Output is correct
6 Correct 70 ms 23892 KB Output is correct
7 Correct 120 ms 27160 KB Output is correct
8 Correct 416 ms 61720 KB Output is correct
9 Correct 131 ms 29464 KB Output is correct
10 Correct 333 ms 52892 KB Output is correct
11 Correct 68 ms 23944 KB Output is correct
12 Correct 332 ms 51924 KB Output is correct
13 Correct 395 ms 61972 KB Output is correct
14 Correct 246 ms 51900 KB Output is correct
15 Correct 257 ms 57892 KB Output is correct
16 Correct 122 ms 28932 KB Output is correct
17 Correct 66 ms 23856 KB Output is correct
18 Correct 313 ms 65944 KB Output is correct
19 Correct 218 ms 50708 KB Output is correct
20 Correct 122 ms 27668 KB Output is correct
21 Correct 68 ms 23856 KB Output is correct
22 Correct 311 ms 65300 KB Output is correct
23 Correct 136 ms 29460 KB Output is correct
24 Correct 344 ms 53676 KB Output is correct
25 Correct 247 ms 53804 KB Output is correct
26 Correct 94 ms 27672 KB Output is correct
27 Correct 102 ms 27164 KB Output is correct
28 Correct 125 ms 28952 KB Output is correct
29 Correct 112 ms 28164 KB Output is correct
30 Correct 136 ms 28796 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 23788 KB Output is correct
2 Correct 69 ms 23856 KB Output is correct
3 Correct 72 ms 23956 KB Output is correct
4 Correct 65 ms 23852 KB Output is correct
5 Correct 66 ms 23836 KB Output is correct
6 Correct 68 ms 24060 KB Output is correct
7 Correct 67 ms 23856 KB Output is correct
8 Correct 73 ms 24064 KB Output is correct
9 Correct 72 ms 23852 KB Output is correct
10 Correct 80 ms 23852 KB Output is correct
11 Correct 69 ms 23856 KB Output is correct
12 Correct 68 ms 23844 KB Output is correct
13 Correct 70 ms 24096 KB Output is correct
14 Correct 67 ms 23868 KB Output is correct
15 Correct 68 ms 23856 KB Output is correct
16 Correct 69 ms 23964 KB Output is correct
17 Correct 65 ms 23856 KB Output is correct
18 Correct 92 ms 23856 KB Output is correct
19 Correct 69 ms 23856 KB Output is correct
20 Correct 67 ms 23832 KB Output is correct
21 Correct 67 ms 23936 KB Output is correct
22 Correct 69 ms 23984 KB Output is correct
23 Correct 66 ms 23852 KB Output is correct
24 Correct 66 ms 23856 KB Output is correct
25 Correct 71 ms 23812 KB Output is correct
26 Correct 135 ms 29144 KB Output is correct
27 Correct 105 ms 27416 KB Output is correct
28 Correct 120 ms 27408 KB Output is correct
29 Correct 98 ms 27148 KB Output is correct
30 Correct 118 ms 28212 KB Output is correct
31 Correct 70 ms 23852 KB Output is correct
32 Correct 105 ms 28184 KB Output is correct
33 Correct 73 ms 24112 KB Output is correct
34 Correct 102 ms 27160 KB Output is correct
35 Correct 100 ms 27156 KB Output is correct
36 Correct 126 ms 29464 KB Output is correct
37 Correct 124 ms 28948 KB Output is correct
38 Correct 68 ms 23856 KB Output is correct
39 Correct 126 ms 28696 KB Output is correct
40 Correct 116 ms 28436 KB Output is correct
41 Correct 132 ms 29440 KB Output is correct
42 Correct 120 ms 28752 KB Output is correct
43 Correct 108 ms 27160 KB Output is correct
44 Correct 69 ms 23852 KB Output is correct
45 Correct 128 ms 27160 KB Output is correct
46 Correct 127 ms 28176 KB Output is correct
47 Correct 66 ms 24076 KB Output is correct
48 Correct 134 ms 29976 KB Output is correct
49 Correct 93 ms 27668 KB Output is correct
50 Correct 100 ms 27140 KB Output is correct
51 Correct 125 ms 28876 KB Output is correct
52 Correct 112 ms 28192 KB Output is correct
53 Correct 114 ms 28696 KB Output is correct
54 Correct 113 ms 28184 KB Output is correct
55 Correct 66 ms 23960 KB Output is correct
56 Correct 276 ms 62996 KB Output is correct
57 Correct 284 ms 51732 KB Output is correct
58 Correct 104 ms 27412 KB Output is correct
59 Correct 67 ms 23904 KB Output is correct
60 Correct 65 ms 23856 KB Output is correct
61 Correct 299 ms 53260 KB Output is correct
62 Correct 101 ms 27156 KB Output is correct
63 Correct 283 ms 48404 KB Output is correct
64 Correct 296 ms 51436 KB Output is correct
65 Correct 125 ms 29452 KB Output is correct
66 Correct 256 ms 48640 KB Output is correct
67 Correct 117 ms 27672 KB Output is correct
68 Correct 126 ms 29208 KB Output is correct
69 Correct 269 ms 58208 KB Output is correct
70 Correct 105 ms 27156 KB Output is correct
71 Correct 286 ms 52776 KB Output is correct
72 Correct 244 ms 47900 KB Output is correct
73 Correct 81 ms 24060 KB Output is correct
74 Correct 260 ms 47780 KB Output is correct
75 Correct 268 ms 52248 KB Output is correct
76 Correct 110 ms 28184 KB Output is correct
77 Correct 117 ms 28180 KB Output is correct
78 Correct 284 ms 63208 KB Output is correct
79 Correct 250 ms 66124 KB Output is correct
80 Correct 122 ms 29032 KB Output is correct
81 Correct 106 ms 27416 KB Output is correct
82 Correct 82 ms 23792 KB Output is correct
83 Correct 70 ms 23892 KB Output is correct
84 Correct 120 ms 27160 KB Output is correct
85 Correct 416 ms 61720 KB Output is correct
86 Correct 131 ms 29464 KB Output is correct
87 Correct 333 ms 52892 KB Output is correct
88 Correct 68 ms 23944 KB Output is correct
89 Correct 332 ms 51924 KB Output is correct
90 Correct 395 ms 61972 KB Output is correct
91 Correct 246 ms 51900 KB Output is correct
92 Correct 257 ms 57892 KB Output is correct
93 Correct 122 ms 28932 KB Output is correct
94 Correct 66 ms 23856 KB Output is correct
95 Correct 313 ms 65944 KB Output is correct
96 Correct 218 ms 50708 KB Output is correct
97 Correct 122 ms 27668 KB Output is correct
98 Correct 68 ms 23856 KB Output is correct
99 Correct 311 ms 65300 KB Output is correct
100 Correct 136 ms 29460 KB Output is correct
101 Correct 344 ms 53676 KB Output is correct
102 Correct 247 ms 53804 KB Output is correct
103 Correct 94 ms 27672 KB Output is correct
104 Correct 102 ms 27164 KB Output is correct
105 Correct 125 ms 28952 KB Output is correct
106 Correct 112 ms 28164 KB Output is correct
107 Correct 136 ms 28796 KB Output is correct
108 Correct 1392 ms 214420 KB Output is correct
109 Correct 1204 ms 144892 KB Output is correct
110 Correct 1194 ms 144872 KB Output is correct
111 Correct 1305 ms 167192 KB Output is correct
112 Correct 1503 ms 188400 KB Output is correct
113 Correct 1361 ms 234864 KB Output is correct
114 Correct 1341 ms 160676 KB Output is correct
115 Correct 1317 ms 158456 KB Output is correct
116 Correct 1446 ms 154904 KB Output is correct
117 Correct 1316 ms 167332 KB Output is correct
118 Correct 1329 ms 154900 KB Output is correct
119 Correct 1294 ms 167488 KB Output is correct
120 Correct 1403 ms 185736 KB Output is correct
121 Correct 1231 ms 169404 KB Output is correct
122 Correct 1567 ms 162468 KB Output is correct
123 Correct 1230 ms 248796 KB Output is correct
124 Correct 1387 ms 166420 KB Output is correct