Submission #1130946

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130946		krishnaar2305	Training (IOI07_training)	C++20	Compilation error	0 ms	0 KiB

training

import sys
from collections import defaultdict, deque

sys.setrecursionlimit(10**6)
MOD = int(1e9+7)
MAXN = 5001
MAXK = 10

n, m, total_sum = 0, 0, 0
par = [(0, 0)] * MAXN
jump = [[0] * (MAXK + 1) for _ in range(MAXN)]
paths = [[] for _ in range(MAXN)]
deg = [0] * MAXN
order = [0] * MAXN
lvl = [0] * MAXN
ptr = 0

class Edge:
    def __init__(self, a, b, c, lca):
        self.a = a
        self.b = b
        self.c = c
        self.lca = lca

    def __lt__(self, other):
        return order[self.lca] < order[other.lca]

edges = []

def dfs(pos=1, p=1):
    global ptr
    jump[pos][0] = p
    for el in paths[pos]:
        if el == p:
            continue
        lvl[el] = lvl[pos] + 1
        par[el] = (pos, 1 << deg[pos])
        deg[pos] += 1
        dfs(el, pos)
    order[pos] = ptr
    ptr += 1

def LCA(a, b):
    if lvl[a] < lvl[b]:
        a, b = b, a
    dist = lvl[a] - lvl[b]
    for j in range(MAXK + 1):
        if dist & (1 << j):
            a = jump[a][j]
    if a == b:
        return a
    for j in range(MAXK, -1, -1):
        if jump[a][j] != jump[b][j]:
            a = jump[a][j]
            b = jump[b][j]
    return jump[a][0]

dp = [[0] * (1 << MAXK) for _ in range(MAXN)]

def solve():
    for edge in edges:
        a, b, cur, lca = edge.a, edge.b, edge.c, edge.lca
        if lvl[a] % 2 != lvl[b] % 2 and cur != 0:
            continue
        mask1, mask2 = 0, 0
        while a != lca:
            cur += dp[a][par[a][1]]
            a, mask1 = par[a]
        while b != lca:
            cur += dp[b][par[b][1]]
            b, mask2 = par[b]
        mask1 |= mask2
        for mask in range((1 << deg[lca]) - 1, -1, -1):
            if mask & mask1:
                continue
            dp[lca][mask] = max(dp[lca][mask], cur + dp[lca][mask | mask1])

if __name__ == "__main__":
    input = sys.stdin.read
    data = input().split()
    n, m = int(data[0]), int(data[1])
    edges_input = data[2:]
    global total_sum
    for i in range(m):
        a, b, c = map(int, edges_input[3 * i:3 * i + 3])
        if c == 0:
            paths[a].append(b)
            paths[b].append(a)
        total_sum += c
        edges.append(Edge(a, b, c, 0))

    par[1] = (1, 0)
    dfs()
    for j in range(1, MAXK + 1):
        for i in range(1, n + 1):
            jump[i][j] = jump[jump[i][j - 1]][j - 1]

    for edge in edges:
        if lvl[edge.a] % 2 != lvl[edge.b] % 2 and edge.c != 0:
            continue
        edge.lca = LCA(edge.a, edge.b)

    edges.sort()
    solve()
    print(total_sum - dp[1][0])

Compilation message (stderr)

training.cpp:1:1: error: 'import' does not name a type
    1 | import sys
      | ^~~~~~
training.cpp:1:1: note: C++20 'import' only available with '-fmodules-ts', which is not yet enabled with '-std=c++20'