結果

問題 No.583 鉄道同好会
ユーザー kohei2019kohei2019
提出日時 2022-02-11 15:05:59
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,704 bytes
コンパイル時間 303 ms
コンパイル使用メモリ 86,868 KB
実行使用メモリ 108,152 KB
最終ジャッジ日時 2023-09-09 16:32:46
合計ジャッジ時間 7,062 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 93 ms
71,504 KB
testcase_01 AC 93 ms
71,488 KB
testcase_02 AC 93 ms
71,280 KB
testcase_03 AC 94 ms
71,360 KB
testcase_04 AC 93 ms
71,608 KB
testcase_05 AC 92 ms
71,596 KB
testcase_06 AC 93 ms
71,576 KB
testcase_07 AC 92 ms
71,504 KB
testcase_08 AC 94 ms
71,488 KB
testcase_09 AC 93 ms
71,608 KB
testcase_10 AC 98 ms
71,956 KB
testcase_11 AC 156 ms
86,192 KB
testcase_12 AC 169 ms
88,296 KB
testcase_13 AC 169 ms
88,432 KB
testcase_14 AC 169 ms
88,620 KB
testcase_15 AC 184 ms
89,516 KB
testcase_16 AC 237 ms
101,576 KB
testcase_17 AC 262 ms
108,152 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