結果

問題 No.583 鉄道同好会
ユーザー kohei2019kohei2019
提出日時 2022-02-11 15:05:59
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,704 bytes
コンパイル時間 239 ms
コンパイル使用メモリ 82,088 KB
実行使用メモリ 112,600 KB
最終ジャッジ日時 2024-06-27 09:17:49
合計ジャッジ時間 5,518 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
61,948 KB
testcase_01 AC 42 ms
54,752 KB
testcase_02 AC 42 ms
55,064 KB
testcase_03 AC 42 ms
54,724 KB
testcase_04 AC 42 ms
54,888 KB
testcase_05 AC 42 ms
54,348 KB
testcase_06 AC 43 ms
55,028 KB
testcase_07 AC 41 ms
55,504 KB
testcase_08 AC 42 ms
54,744 KB
testcase_09 AC 42 ms
55,100 KB
testcase_10 AC 46 ms
55,964 KB
testcase_11 AC 109 ms
84,080 KB
testcase_12 AC 126 ms
88,740 KB
testcase_13 AC 124 ms
88,724 KB
testcase_14 AC 120 ms
88,836 KB
testcase_15 AC 135 ms
91,924 KB
testcase_16 AC 188 ms
101,468 KB
testcase_17 AC 214 ms
106,604 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

def main():
    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')
main()
0