結果

問題 No.583 鉄道同好会
ユーザー kohei2019kohei2019
提出日時 2022-02-11 15:04:07
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,673 bytes
コンパイル時間 951 ms
コンパイル使用メモリ 86,476 KB
実行使用メモリ 108,272 KB
最終ジャッジ日時 2023-09-09 16:30:39
合計ジャッジ時間 8,221 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 97 ms
71,376 KB
testcase_02 AC 100 ms
71,292 KB
testcase_03 WA -
testcase_04 AC 97 ms
71,116 KB
testcase_05 AC 99 ms
71,288 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 AC 97 ms
71,288 KB
testcase_09 AC 96 ms
71,536 KB
testcase_10 AC 101 ms
72,172 KB
testcase_11 AC 179 ms
86,116 KB
testcase_12 AC 177 ms
88,368 KB
testcase_13 AC 179 ms
88,200 KB
testcase_14 AC 177 ms
88,448 KB
testcase_15 AC 190 ms
89,440 KB
testcase_16 AC 245 ms
101,832 KB
testcase_17 AC 275 ms
108,272 KB
testcase_18 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import Counter

# Edges := [Edge*]
# Edge := (Vertex, Vertex)
# Vertex := Hashable except None

def solve_hitofude(edges):
    def _make_vertexcounter(edges):
        '各頂点ごとに、辺の数を数える'
        c = Counter()
        for x, y in edges:
            c[x] += 1
            c[y] += 1
        return c

    def _make_edgeflag(edges, value=True):
        '通った辺を管理するための辞書を作る'
        d = dict()
        for edge in edges:
            d[edge] = value
        return d

    def _get_head_tail(counter):
        '始点・終点を決める'
        odd = []
        for k,v in counter.items():
            if v&1: odd.append(k)
        if len(odd) == 2:
            return tuple(odd)
        elif len(odd) == 0:
            t = c.most_common(1)[0][0]
            return t, t
        else:
            return None, None

    def _edge_selector(pos, edgeflag):
        'ジェネレータ関数。ある点につながっていて、まだ通ってない辺をyieldするジェネレータを作る。'
        for edge in edgeflag:
            if edgeflag[edge]:
                a, b = edge
                if a == pos:
                    yield edge, b
                if edgeflag[edge] and b == pos:
                    yield edge, a

    stack_pos = []  # 通った点を順に入れていく
    stack_edge = []  # 通った辺を入れていく
    stack_selector = []  # _edge_selectorジェネレータを入れていく

    c = _make_vertexcounter(edges)
    remain = _make_edgeflag(edges)

    pos, tail = _get_head_tail(c)
    if pos is None:
        return None
    n = len(edges)
    selector = _edge_selector(pos, remain)

    while n:  # 全部の辺をたどったら終了
        try:
            edge, nextpos = next(selector)
        except StopIteration:  # 辿れる辺がなくなったら戻る。これ以上戻れない場合はNoneを返す。
            if stack_pos:
                pos = stack_pos.pop()
                remain[stack_edge.pop()] = True
                selector = stack_selector.pop()
                n += 1
            else:
                return None
        else:  # 辿れる場合の処理。
            stack_pos.append(pos)
            stack_edge.append(edge)
            stack_selector.append(selector)
            pos = nextpos
            remain[edge] = False
            selector = _edge_selector(pos, remain)
            n -= 1
    if pos == tail:
        return stack_pos, stack_edge
    assert False

N,M = map(int,input().split())
lsedg = [tuple(map(int,input().split())) for i in range(M)]
print('NO' if solve_hitofude(lsedg)==None else 'Yes')
0