Submission #1048128

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1048128	2024-08-07T23:56:42 Z	RauPro	Mergers (JOI19_mergers)	C++14	Compilation error	0 ms	0 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
    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])

    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(ans)
    #print(AL_aux)
    print((ans + 1) // 2)




if __name__ == "__main__":
    main()

Compilation message

mergers.cpp:13:3: error: invalid preprocessing directive #Para
   13 | # Para mejorar el rendimiento de la entrada/salida
      |   ^~~~
mergers.cpp:18:3: error: invalid preprocessing directive #Optimizaci\U000000f3n
   18 | # Optimización de la recursión para Python
      |   ^~~~~~~~~~~~
mergers.cpp:22:3: error: invalid preprocessing directive #Funciones
   22 | # Funciones para lectura de múltiples tipos de datos
      |   ^~~~~~~~~
mergers.cpp:26:54: error: stray '#' in program
   26 | 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
      |                                                      ^
mergers.cpp:29:3: error: invalid preprocessing directive #Constantes
   29 | # Constantes útiles
      |   ^~~~~~~~~~
mergers.cpp:30:13: warning: multi-character character constant [-Wmultichar]
   30 | INF = float('inf')
      |             ^~~~~
mergers.cpp:31:19: error: stray '#' in program
   31 | MOD = 1000000007  # Modulo por defecto, cambiar si se necesita otro
      |                   ^
mergers.cpp:34:3: error: invalid preprocessing directive #Algunas
   34 | # Algunas funciones útiles
      |   ^~~~~~~
mergers.cpp:39:3: error: invalid preprocessing directive #Inverso
   39 | # Inverso multiplicativo de a modulo m (cuando m es primo)
      |   ^~~~~~~
mergers.cpp:87:3: error: invalid preprocessing directive #Tree
   87 | # Tree compression from vertex a to b
      |   ^~~~
mergers.cpp:122:6: error: invalid preprocessing directive #print
  122 |     #print(tree_groups)
      |      ^~~~~
mergers.cpp:128:6: error: invalid preprocessing directive #print
  128 |     #print(depth, parent)
      |      ^~~~~
mergers.cpp:141:6: error: invalid preprocessing directive #print
  141 |     #print(ans)
      |      ^~~~~
mergers.cpp:142:6: error: invalid preprocessing directive #print
  142 |     #print(AL_aux)
      |      ^~~~~
mergers.cpp:1:1: error: 'import' does not name a type
    1 | import os
      | ^~~~~~