Submission #1130950

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130950		krishnaar2305	Training (IOI07_training)	Pypy 3	100 / 100	282 ms	88892 KiB

training

import sys
from collections import defaultdict

sys.setrecursionlimit(10**6)

# Constants
MAXN = 5001
MAXK = 10

# Global variables
dp = [[0] * (1 << 10) for _ in range(MAXN)]
in_time = [0] * MAXN
out_time = [0] * MAXN
lol = [0] * MAXN
deg = [0] * MAXN
adj = defaultdict(list)
pr = [(0, 0)] * MAXN
timer = 0

class Road:
    def __init__(self, l, r, cost, lca=0):
        self.l = l
        self.r = r
        self.cost = cost
        self.lca = lca

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

def dfs(node, parent):
    global timer
    timer += 1
    in_time[node] = timer
    lol[node] = lol[parent] ^ 1
    for neighbor in adj[node]:
        if neighbor != parent:
            pr[neighbor] = (node, 1 << deg[node])
            deg[node] += 1
            dfs(neighbor, node)
    timer += 1
    out_time[node] = timer

def is_parent(A, B):
    return in_time[A] <= in_time[B] and out_time[A] >= out_time[B]

def find_lca(A, B):
    while not is_parent(A, B):
        A = pr[A][0]
    return A

def main():
    input = sys.stdin.read
    data = input().split()
    n, m = int(data[0]), int(data[1])
    roads = []
    total_cost = 0

    idx = 2
    for _ in range(m):
        a, b, c = map(int, data[idx:idx+3])
        idx += 3
        total_cost += c
        if c == 0:
            adj[a].append(b)
            adj[b].append(a)
        roads.append(Road(a, b, c))

    dfs(1, 0)

    for road in roads:
        road.lca = find_lca(road.l, road.r)

    roads.sort()

    for road in roads:
        if road.cost and (lol[road.l] ^ lol[road.r]) == 1:
            continue

        cost_accumulated = road.cost
        A, B = (road.l, 0), (road.r, 0)

        while A[0] != road.lca:
            cost_accumulated += dp[A[0]][A[1]]
            A = pr[A[0]]

        while B[0] != road.lca:
            cost_accumulated += dp[B[0]][B[1]]
            B = pr[B[0]]

        for mask in range((1 << deg[road.lca]) - 1, -1, -1):
            if mask & (A[1] | B[1]) == 0:
                dp[road.lca][mask] = max(
                    dp[road.lca][mask],
                    cost_accumulated + dp[road.lca][mask | A[1] | B[1]]
                )

    print(total_cost - dp[1][0])

if __name__ == "__main__":
    main()

Compilation message (stdout)

Compiling 'training.py'...

=======
  adding: __main__.pyc (deflated 44%)

=======

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 7 / 7
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9