AtCoder Regular Contest 078

Submission #1427667

Source codeソースコード

import sys
readline = sys.stdin.readline
from heapq import heappush, heappop
from collections import deque

N = int(readline())
edges = [[] for _ in [None]*N]
for _ in [None]*(N-1):
    a,b = map(int, readline().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)


def dijkstra(n, edges, start, stop):
    inf = float("inf")
    vertices = [(inf,None) for _ in [None]*n]
    vertices[start] = (0, None)
    q = [(0, start)]

    while q:
        cost, v = heappop(q)
        if vertices[v][0] < cost:
            continue

        for dest in edges[v]:
            newcost = cost + 1
            if vertices[dest][0] > newcost:
                vertices[dest] = (newcost, v)
                if not dest in stop:
                    heappush(q, (newcost, dest))
    return vertices

def hoge(start, stop):
    dq = deque()
    pop, append = dq.popleft, dq.append
    cnt = 0
    visited = [0]*N
    append(start)
    while dq:
        pos = pop()
        for v in edges[pos]:
            if visited[v] == 0 and v not in stop:
                append(v)
                visited[v] = 1
                cnt += 1
    return cnt

vs = dijkstra(N, edges, 0, {N-1})
path = []
ap = path.append
n = vs[N-1][1]
while n != 0:
    ap(n)
    n = vs[n][1]

import math
x = math.ceil(len(path)/2)
fen_s = set(path[-x:]+[0])
snuke_s = set(path[:-x]+[N-1])
fen = hoge(0, snuke_s)
snuke = hoge(N-1, fen_s)
#print(fen, snuke, path, fen_s, snuke_s)
print("Fennec" if fen > snuke else "Snuke")

Submission

Task問題 D - Fennec VS. Snuke
User nameユーザ名 htkb
Created time投稿日時
Language言語 Python3 (3.4.3)
Status状態 AC
Score得点 400
Source lengthソースコード長 1543 Byte
File nameファイル名
Exec time実行時間 583 ms
Memory usageメモリ使用量 40792 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - 00_example_01.txt,00_example_02.txt
All 400 / 400 00_example_01.txt,00_example_02.txt,01.txt,02.txt,03.txt,04.txt,05.txt,06.txt,07.txt,08.txt,09.txt,10.txt,11.txt,12.txt,13.txt,14.txt,15.txt,16.txt,17.txt,18.txt,19.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_example_01.txt AC 21 ms 3316 KB
00_example_02.txt AC 21 ms 3316 KB
01.txt AC 21 ms 3316 KB
02.txt AC 21 ms 3316 KB
03.txt AC 21 ms 3316 KB
04.txt AC 21 ms 3316 KB
05.txt AC 400 ms 31448 KB
06.txt AC 418 ms 31404 KB
07.txt AC 416 ms 29316 KB
08.txt AC 421 ms 31288 KB
09.txt AC 21 ms 3316 KB
10.txt AC 453 ms 27232 KB
11.txt AC 477 ms 27704 KB
12.txt AC 524 ms 29360 KB
13.txt AC 570 ms 30472 KB
14.txt AC 583 ms 30608 KB
15.txt AC 542 ms 30476 KB
16.txt AC 491 ms 40792 KB
17.txt AC 501 ms 38756 KB
18.txt AC 485 ms 38660 KB
19.txt AC 485 ms 38756 KB