東京大学プログラミングコンテスト2014

Submission #6919866

Source codeソースコード

import sys
sys.setrecursionlimit(10**7)


n = int(input())
edge = {}
for i in range(n):
    a, b = map(int, input().split())
    if a in edge:
        edge[a].append(b)
    else:
        edge[a] = [b]

    if b in edge:
        edge[b].append(a)
    else:
        edge[b] = [a]

visited = []
def dfs(now, prev):
    if now in visited:
        print_ans(len(visited) - visited.index(now))
        exit()
    else:
        for e in edge[now]:
            if e == prev:
                continue
            visited.append(now)
            ret = dfs(e, now)
            visited.pop()
    return

def print_ans(length):
    ans_min = 1
    ans_max = n
    if length == n:
        ans_min = 2
        
    if length % 2 == 1:
        ans_max = n-1
        
    print(str(ans_min) + ' ' + str(ans_max))
    
dfs(1, 1)

Submission

Task問題 C - 最小カットと最大カット
User nameユーザ名 tsb2b
Created time投稿日時
Language言語 PyPy3 (2.4.0)
Status状態 TLE
Score得点 0
Source lengthソースコード長 855 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
All 0 / 100 scrambled_00.txt,scrambled_01.txt,scrambled_02.txt,scrambled_03.txt,scrambled_04.txt,scrambled_05.txt,scrambled_06.txt,scrambled_07.txt,scrambled_08.txt,scrambled_09.txt,scrambled_10.txt,scrambled_11.txt,scrambled_12.txt,scrambled_13.txt,scrambled_14.txt,scrambled_15.txt,scrambled_16.txt,scrambled_17.txt,scrambled_18.txt,scrambled_19.txt,scrambled_20.txt,scrambled_21.txt,scrambled_22.txt,scrambled_23.txt,scrambled_24.txt,scrambled_25.txt,scrambled_26.txt,scrambled_27.txt,scrambled_28.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
scrambled_00.txt AC 170 ms 38512 KB
scrambled_01.txt AC 172 ms 38384 KB
scrambled_02.txt AC 168 ms 38256 KB
scrambled_03.txt TLE
scrambled_04.txt TLE
scrambled_05.txt AC 1937 ms 104768 KB
scrambled_06.txt AC 993 ms 83672 KB
scrambled_07.txt TLE
scrambled_08.txt AC 755 ms 76248 KB
scrambled_09.txt AC 1044 ms 85464 KB
scrambled_10.txt AC 649 ms 68440 KB
scrambled_11.txt AC 400 ms 52952 KB
scrambled_12.txt AC 544 ms 59096 KB
scrambled_13.txt AC 554 ms 58712 KB
scrambled_14.txt AC 817 ms 77912 KB
scrambled_15.txt AC 620 ms 61656 KB
scrambled_16.txt AC 457 ms 55768 KB
scrambled_17.txt AC 429 ms 55128 KB
scrambled_18.txt AC 700 ms 68696 KB
scrambled_19.txt AC 308 ms 49240 KB
scrambled_20.txt AC 611 ms 64984 KB
scrambled_21.txt AC 415 ms 53976 KB
scrambled_22.txt AC 603 ms 59224 KB
scrambled_23.txt AC 453 ms 56152 KB
scrambled_24.txt AC 435 ms 55768 KB
scrambled_25.txt AC 482 ms 56920 KB
scrambled_26.txt AC 462 ms 56408 KB
scrambled_27.txt AC 529 ms 58208 KB
scrambled_28.txt AC 509 ms 57304 KB