結果

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

ソースコード

diff #
raw source code 

import pypyjit
pypyjit.set_param("max_unroll_recursion=-1")
import sys
sys.setrecursionlimit(10**5 + 100)


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):
        if(len(ans) >= 4):
            ans.pop()
            print(len(ans))
            print(*ans)
            exit()
        elif(len(ans) >= 2):
            return
    visited.add((n,mode))

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

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

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

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

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