Submission #1169986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169986		mst_molik	Training (IOI07_training)	Pypy 3	0 / 100	137 ms	48840 KiB

training

from collections import defaultdict
import sys

sys.setrecursionlimit(2000)

def dfs(node, color):
    global is_bipartite
    colors[node] = color
    for neighbor in tree_graph[node]:
        if colors[neighbor] == -1:
            dfs(neighbor, color ^ 1)
        elif colors[neighbor] == color:
            is_bipartite = False  # Not expected in a tree but safe to check

def solve():
    # Read input
    N, M = map(int, input().split())

    tree_graph = defaultdict(list)
    unpaved_edges = []
    
    # Read roads
    for _ in range(M):
        A, B, C = map(int, input().split())
        if C == 0:
            tree_graph[A].append(B)
            tree_graph[B].append(A)
        else:
            unpaved_edges.append((C, A, B))
    
    # Step 1: Color the tree using DFS
    global colors, is_bipartite
    colors = [-1] * (N + 1)
    is_bipartite = True

    dfs(1, 0)  # Start coloring from node 1

    # Step 2: Identify even-cycle unpaved roads
    valid_unpaved = []
    
    for cost, A, B in unpaved_edges:
        if colors[A] != colors[B]:  # Different colors => Even-length cycle
            valid_unpaved.append(cost)

    # Step 3: Find minimum cost to block all even-cycle edges
    print(sum(valid_unpaved))  # Sum of all valid edges

Compilation message (stdout)

Compiling 'training.py'...

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

=======

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