답안 #1048124

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1048124	2024-08-07T23:46:53 Z	RauPro	Mergers (JOI19_mergers)	PyPy 3	34 / 100	545 ms	262144 KB

mergers

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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #1048124

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