結果

問題 No.1647 Travel in Mitaru city 2
コンテスト
ユーザー 回転
提出日時 2026-07-28 14:36:13
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 2,102 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,603 ms
コンパイル使用メモリ 95,212 KB
実行使用メモリ 258,816 KB
最終ジャッジ日時 2026-07-28 14:36:41
合計ジャッジ時間 26,814 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18 WA * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import pypyjit
pypyjit.set_param("max_unroll_recursion=-1")
import sys
sys.setrecursionlimit(2*10**5)
from collections import defaultdict
H,W,N = list(map(int,input().split()))
y_is = defaultdict(list)
x_is = defaultdict(list)
to_num = defaultdict(lambda:None)
for i in range(N):
    y,x = list(map(int,input().split()))
    y_is[y].append(x)
    x_is[x].append(y)
    to_num[(y,x)] = i

for i in y_is:y_is[i].sort()
for i in x_is:x_is[i].sort()

edge_yoko = [[] for _ in range(N)]
for x in x_is:
    S = len(x_is[x])
    for j in range(S):
        y = x_is[x][j]
        num = to_num[(y,x)]
        if(j+1 < S):
            yy = x_is[x][j+1]
            next_num = to_num[(yy,x)]
            edge_yoko[num].append(next_num)
            edge_yoko[next_num].append(num)
        if(j+2 < S):
            yyy = x_is[x][j+2]
            next_next_num = to_num[(yyy,x)]
            edge_yoko[num].append(next_next_num)
            edge_yoko[next_next_num].append(num)

edge_tate = [[] for _ in range(N)]
for y in y_is:
    S = len(y_is[y])
    for j in range(S):
        x = y_is[y][j]
        num = to_num[(y,x)]
        if(j+1 < S):
            xx = y_is[y][j+1]
            next_num = to_num[(y,xx)]
            edge_tate[num].append(next_num)
            edge_tate[next_num].append(num)
        if(j+2 < S):
            xxx = y_is[y][j+2]
            next_next_num = to_num[(y,xxx)]
            edge_tate[num].append(next_next_num)
            edge_tate[next_next_num].append(num)

ans = []
visited = set()
def dfs(n,pre,mode):
    if(n == 0 and len(ans) >= 4):
        ans.pop()
        print(len(ans))
        print(*ans)
        exit()
    visited.add(n)

    if(mode):
        for i in edge_yoko[n]:
            if(i == pre):continue
            if(i != 0 and i in visited):continue
            ans.append(i+1)
            dfs(i,n,False)
            ans.pop()
    else:
        for i in edge_tate[n]:
            if(i == pre):continue
            if(i != 0 and i in visited):continue
            ans.append(i+1)
            dfs(i,n,True)
            ans.pop()

ans.append(1)
dfs(0,-1,True)
print(-1)
0