Submission #1273288

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273288		anhkhoa	Tram (CEOI13_tram)	Pypy 3	0 / 100	167 ms	52880 KiB

tram

import sys
from collections import defaultdict, deque

def solve():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx += 1
    M = int(input[idx]); idx += 1  
    K = int(input[idx]); idx += 1
    
    graph = defaultdict(list)
    
    # Add main line tracks
    for i in range(1, N):
        graph[i].append(i+1)
        graph[i+1].append(i)
    
    # Add additional tracks
    for _ in range(K):
        u = int(input[idx]); idx += 1
        v = int(input[idx]); idx += 1
        graph[u].append(v)
        graph[v].append(u)
    
    # Check degrees
    for i in range(1, N+1):
        if len(graph[i]) > 2:
            print(-1)
            return
    
    visited = [False] * (N+1)
    components = []
    cycles = 0
    
    for i in range(1, N+1):
        if not visited[i]:
            # BFS/DFS to find component
            comp = []
            stack = [i]
            visited[i] = True
            
            while stack:
                node = stack.pop()
                comp.append(node)
                for neighbor in graph[node]:
                    if not visited[neighbor]:
                        visited[neighbor] = True
                        stack.append(neighbor)
            
            components.append(comp)
            
            # Check if component is a cycle
            is_cycle = True
            for node in comp:
                if len(graph[node]) != 2:
                    is_cycle = False
                    break
            if is_cycle:
                cycles += 1
    
    if cycles > 1:
        print(-1)
        return
    
    if cycles == 1:
        if len(components) == 1:
            print(0)
        else:
            print(-1)
        return
    
    # No cycles, only paths
    print(len(components))

if __name__ == "__main__":
    solve()

Compilation message (stdout)

Compiling 'tram.py'...

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

=======

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 15
• Subtask 8: 0 / 20