oj.uz

Submission #1048124

# Submission time Handle Problem Language Result Execution time Memory
1048124 2024-08-07T23:46:53 Z RauPro Mergers (JOI19_mergers) PyPy 3
34 / 100
 545 ms 262144 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
    visited[u] = True
    depth[u] = lvl
    parent[u] = p
    for v in AL[u]:
        if not visited[v]:
            dfs(v, lvl+1, u)
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])

    AL_aux = [set() for i in range(n+1)]
    for u in range(1, n+1):
        for v in AL[u]:
            if uf.find(u) != uf.find(v):
                AL_aux[uf.find(u)].add(uf.find(v))
    ans = sum([1 for it in AL_aux if len(it) == 1])
    #print(AL_aux)
    print((ans + 1) // 2)




if __name__ == "__main__":
    main()

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 23844 KB Output is correct
2 Correct 68 ms 24112 KB Output is correct
3 Correct 67 ms 23876 KB Output is correct
4 Correct 75 ms 23848 KB Output is correct
5 Correct 68 ms 23852 KB Output is correct
6 Correct 67 ms 23852 KB Output is correct
7 Correct 70 ms 23856 KB Output is correct
8 Correct 70 ms 23980 KB Output is correct
9 Correct 69 ms 23852 KB Output is correct
10 Correct 74 ms 23856 KB Output is correct
11 Correct 67 ms 24084 KB Output is correct
12 Correct 68 ms 23852 KB Output is correct
13 Correct 67 ms 23900 KB Output is correct
14 Correct 67 ms 23856 KB Output is correct
15 Correct 69 ms 24088 KB Output is correct
16 Correct 66 ms 23964 KB Output is correct
17 Correct 68 ms 24112 KB Output is correct
18 Correct 78 ms 23856 KB Output is correct
19 Correct 75 ms 24148 KB Output is correct
20 Correct 68 ms 23828 KB Output is correct
21 Correct 69 ms 23856 KB Output is correct
22 Correct 69 ms 24088 KB Output is correct
23 Correct 68 ms 23908 KB Output is correct
24 Correct 68 ms 24108 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 23844 KB Output is correct
2 Correct 68 ms 24112 KB Output is correct
3 Correct 67 ms 23876 KB Output is correct
4 Correct 75 ms 23848 KB Output is correct
5 Correct 68 ms 23852 KB Output is correct
6 Correct 67 ms 23852 KB Output is correct
7 Correct 70 ms 23856 KB Output is correct
8 Correct 70 ms 23980 KB Output is correct
9 Correct 69 ms 23852 KB Output is correct
10 Correct 74 ms 23856 KB Output is correct
11 Correct 67 ms 24084 KB Output is correct
12 Correct 68 ms 23852 KB Output is correct
13 Correct 67 ms 23900 KB Output is correct
14 Correct 67 ms 23856 KB Output is correct
15 Correct 69 ms 24088 KB Output is correct
16 Correct 66 ms 23964 KB Output is correct
17 Correct 68 ms 24112 KB Output is correct
18 Correct 78 ms 23856 KB Output is correct
19 Correct 75 ms 24148 KB Output is correct
20 Correct 68 ms 23828 KB Output is correct
21 Correct 69 ms 23856 KB Output is correct
22 Correct 69 ms 24088 KB Output is correct
23 Correct 68 ms 23908 KB Output is correct
24 Correct 68 ms 24108 KB Output is correct
25 Correct 68 ms 23852 KB Output is correct
26 Correct 141 ms 31768 KB Output is correct
27 Correct 140 ms 33304 KB Output is correct
28 Correct 118 ms 30232 KB Output is correct
29 Correct 108 ms 28156 KB Output is correct
30 Correct 127 ms 29512 KB Output is correct
31 Correct 67 ms 23900 KB Output is correct
32 Correct 135 ms 53272 KB Output is correct
33 Correct 68 ms 24112 KB Output is correct
34 Correct 108 ms 26904 KB Output is correct
35 Correct 103 ms 28180 KB Output is correct
36 Correct 131 ms 30480 KB Output is correct
37 Correct 134 ms 31064 KB Output is correct
38 Correct 67 ms 23924 KB Output is correct
39 Correct 137 ms 30220 KB Output is correct
40 Correct 124 ms 29716 KB Output is correct
41 Correct 132 ms 31000 KB Output is correct
42 Correct 122 ms 28436 KB Output is correct
43 Correct 110 ms 33560 KB Output is correct
44 Correct 68 ms 24256 KB Output is correct
45 Correct 125 ms 36888 KB Output is correct
46 Correct 125 ms 29284 KB Output is correct
47 Correct 69 ms 24088 KB Output is correct
48 Correct 137 ms 31512 KB Output is correct
49 Correct 96 ms 27416 KB Output is correct
50 Correct 138 ms 53284 KB Output is correct
51 Correct 133 ms 30228 KB Output is correct
52 Correct 112 ms 27668 KB Output is correct
53 Correct 123 ms 27852 KB Output is correct
54 Correct 120 ms 29480 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 23844 KB Output is correct
2 Correct 68 ms 24112 KB Output is correct
3 Correct 67 ms 23876 KB Output is correct
4 Correct 75 ms 23848 KB Output is correct
5 Correct 68 ms 23852 KB Output is correct
6 Correct 67 ms 23852 KB Output is correct
7 Correct 70 ms 23856 KB Output is correct
8 Correct 70 ms 23980 KB Output is correct
9 Correct 69 ms 23852 KB Output is correct
10 Correct 74 ms 23856 KB Output is correct
11 Correct 67 ms 24084 KB Output is correct
12 Correct 68 ms 23852 KB Output is correct
13 Correct 67 ms 23900 KB Output is correct
14 Correct 67 ms 23856 KB Output is correct
15 Correct 69 ms 24088 KB Output is correct
16 Correct 66 ms 23964 KB Output is correct
17 Correct 68 ms 24112 KB Output is correct
18 Correct 78 ms 23856 KB Output is correct
19 Correct 75 ms 24148 KB Output is correct
20 Correct 68 ms 23828 KB Output is correct
21 Correct 69 ms 23856 KB Output is correct
22 Correct 69 ms 24088 KB Output is correct
23 Correct 68 ms 23908 KB Output is correct
24 Correct 68 ms 24108 KB Output is correct
25 Correct 68 ms 23888 KB Output is correct
26 Correct 264 ms 55376 KB Output is correct
27 Correct 345 ms 56084 KB Output is correct
28 Correct 119 ms 32792 KB Output is correct
29 Correct 90 ms 23860 KB Output is correct
30 Correct 90 ms 23936 KB Output is correct
31 Correct 340 ms 59008 KB Output is correct
32 Correct 114 ms 26904 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

# Verdict Execution time Memory Grader output
1 Correct 278 ms 54028 KB Output is correct
2 Correct 297 ms 88344 KB Output is correct
3 Correct 134 ms 31768 KB Output is correct
4 Correct 121 ms 32792 KB Output is correct
5 Correct 70 ms 24208 KB Output is correct
6 Correct 83 ms 23852 KB Output is correct
7 Correct 104 ms 26976 KB Output is correct
8 Correct 460 ms 69868 KB Output is correct
9 Correct 138 ms 30488 KB Output is correct
10 Correct 379 ms 62484 KB Output is correct
11 Correct 73 ms 24112 KB Output is correct
12 Correct 371 ms 69000 KB Output is correct
13 Correct 477 ms 70164 KB Output is correct
14 Correct 335 ms 82200 KB Output is correct
15 Correct 264 ms 56856 KB Output is correct
16 Correct 135 ms 28444 KB Output is correct
17 Correct 66 ms 24036 KB Output is correct
18 Correct 310 ms 86644 KB Output is correct
19 Runtime error 545 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 66 ms 23844 KB Output is correct
2 Correct 68 ms 24112 KB Output is correct
3 Correct 67 ms 23876 KB Output is correct
4 Correct 75 ms 23848 KB Output is correct
5 Correct 68 ms 23852 KB Output is correct
6 Correct 67 ms 23852 KB Output is correct
7 Correct 70 ms 23856 KB Output is correct
8 Correct 70 ms 23980 KB Output is correct
9 Correct 69 ms 23852 KB Output is correct
10 Correct 74 ms 23856 KB Output is correct
11 Correct 67 ms 24084 KB Output is correct
12 Correct 68 ms 23852 KB Output is correct
13 Correct 67 ms 23900 KB Output is correct
14 Correct 67 ms 23856 KB Output is correct
15 Correct 69 ms 24088 KB Output is correct
16 Correct 66 ms 23964 KB Output is correct
17 Correct 68 ms 24112 KB Output is correct
18 Correct 78 ms 23856 KB Output is correct
19 Correct 75 ms 24148 KB Output is correct
20 Correct 68 ms 23828 KB Output is correct
21 Correct 69 ms 23856 KB Output is correct
22 Correct 69 ms 24088 KB Output is correct
23 Correct 68 ms 23908 KB Output is correct
24 Correct 68 ms 24108 KB Output is correct
25 Correct 68 ms 23852 KB Output is correct
26 Correct 141 ms 31768 KB Output is correct
27 Correct 140 ms 33304 KB Output is correct
28 Correct 118 ms 30232 KB Output is correct
29 Correct 108 ms 28156 KB Output is correct
30 Correct 127 ms 29512 KB Output is correct
31 Correct 67 ms 23900 KB Output is correct
32 Correct 135 ms 53272 KB Output is correct
33 Correct 68 ms 24112 KB Output is correct
34 Correct 108 ms 26904 KB Output is correct
35 Correct 103 ms 28180 KB Output is correct
36 Correct 131 ms 30480 KB Output is correct
37 Correct 134 ms 31064 KB Output is correct
38 Correct 67 ms 23924 KB Output is correct
39 Correct 137 ms 30220 KB Output is correct
40 Correct 124 ms 29716 KB Output is correct
41 Correct 132 ms 31000 KB Output is correct
42 Correct 122 ms 28436 KB Output is correct
43 Correct 110 ms 33560 KB Output is correct
44 Correct 68 ms 24256 KB Output is correct
45 Correct 125 ms 36888 KB Output is correct
46 Correct 125 ms 29284 KB Output is correct
47 Correct 69 ms 24088 KB Output is correct
48 Correct 137 ms 31512 KB Output is correct
49 Correct 96 ms 27416 KB Output is correct
50 Correct 138 ms 53284 KB Output is correct
51 Correct 133 ms 30228 KB Output is correct
52 Correct 112 ms 27668 KB Output is correct
53 Correct 123 ms 27852 KB Output is correct
54 Correct 120 ms 29480 KB Output is correct
55 Correct 68 ms 23888 KB Output is correct
56 Correct 264 ms 55376 KB Output is correct
57 Correct 345 ms 56084 KB Output is correct
58 Correct 119 ms 32792 KB Output is correct
59 Correct 90 ms 23860 KB Output is correct
60 Correct 90 ms 23936 KB Output is correct
61 Correct 340 ms 59008 KB Output is correct
62 Correct 114 ms 26904 KB Output is correct
63 Runtime error 397 ms 262144 KB Execution killed with signal 9
64 Halted 0 ms 0 KB -