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

Submission #6919568

Source codeソースコード

from collections import defaultdict

n = int(input())
edge = defaultdict(list)
for i in range(n):
    a, b = map(int, input().split())
    edge[a].append(b)
    edge[b].append(a)

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

loop_length = dfs(1, 1)
ans_min = 1
ans_max = n
if loop_length == n:
    ans_min = 2

if loop_length % 2 == 1:
    ans_max = n-1

print(str(ans_min) + ' ' + str(ans_max))

Submission

Task問題 C - 最小カットと最大カット
User nameユーザ名 tsb2b
Created time投稿日時
Language言語 PyPy3 (2.4.0)
Status状態 RE
Score得点 0
Source lengthソースコード長 735 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 167 ms 38384 KB
scrambled_01.txt AC 170 ms 38256 KB
scrambled_02.txt AC 167 ms 38256 KB
scrambled_03.txt RE
scrambled_04.txt RE
scrambled_05.txt RE
scrambled_06.txt RE
scrambled_07.txt RE
scrambled_08.txt RE
scrambled_09.txt RE
scrambled_10.txt AC 650 ms 71384 KB
scrambled_11.txt AC 407 ms 54104 KB
scrambled_12.txt AC 566 ms 61528 KB
scrambled_13.txt AC 540 ms 61272 KB
scrambled_14.txt AC 830 ms 80344 KB
scrambled_15.txt AC 649 ms 62552 KB
scrambled_16.txt AC 452 ms 56792 KB
scrambled_17.txt AC 444 ms 56280 KB
scrambled_18.txt AC 708 ms 69848 KB
scrambled_19.txt AC 321 ms 50264 KB
scrambled_20.txt AC 619 ms 64856 KB
scrambled_21.txt AC 440 ms 55256 KB
scrambled_22.txt AC 571 ms 60376 KB
scrambled_23.txt AC 468 ms 57432 KB
scrambled_24.txt AC 443 ms 56920 KB
scrambled_25.txt AC 503 ms 58200 KB
scrambled_26.txt AC 472 ms 57688 KB
scrambled_27.txt AC 566 ms 59224 KB
scrambled_28.txt AC 537 ms 58456 KB