結果

問題 No.1865 Make Cycle
ユーザー LyricalMaestroLyricalMaestro
提出日時 2024-11-02 13:07:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 785 ms / 3,000 ms
コード長 1,788 bytes
コンパイル時間 501 ms
コンパイル使用メモリ 82,716 KB
実行使用メモリ 111,932 KB
最終ジャッジ日時 2024-11-02 13:07:19
合計ジャッジ時間 12,955 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 504 ms
94,748 KB
testcase_01 AC 362 ms
93,020 KB
testcase_02 AC 589 ms
98,836 KB
testcase_03 AC 452 ms
98,776 KB
testcase_04 AC 675 ms
111,932 KB
testcase_05 AC 222 ms
86,404 KB
testcase_06 AC 480 ms
101,064 KB
testcase_07 AC 486 ms
97,916 KB
testcase_08 AC 454 ms
100,152 KB
testcase_09 AC 186 ms
85,764 KB
testcase_10 AC 654 ms
104,804 KB
testcase_11 AC 687 ms
105,884 KB
testcase_12 AC 469 ms
96,116 KB
testcase_13 AC 534 ms
94,600 KB
testcase_14 AC 484 ms
99,368 KB
testcase_15 AC 667 ms
101,296 KB
testcase_16 AC 576 ms
101,800 KB
testcase_17 AC 198 ms
84,820 KB
testcase_18 AC 231 ms
86,820 KB
testcase_19 AC 785 ms
106,360 KB
testcase_20 AC 42 ms
54,256 KB
testcase_21 AC 42 ms
53,936 KB
testcase_22 AC 41 ms
55,228 KB
testcase_23 AC 41 ms
54,660 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/1865

from collections import deque

MAX_INT = 10 ** 18

def exists_cycle(N, next_nodes, border):
    passed = [False] * N
    passed2 = [False] * N
    for s in range(N):
        if not passed[s]:
            passed[s] = True
            stack = deque()
            stack.append((s, 0))

            while len(stack) > 0:
                v, index = stack.pop()
                passed2[v] = True

                while index < len(next_nodes[v]):
                    w, i = next_nodes[v][index]
                    if i > border:
                        index += 1
                        continue

                    if passed[w]:
                        if passed2[w]:
                            return True
                        else:
                            index += 1
                            continue

                    stack.append((v, index + 1))
                    stack.append((w, 0))
                    passed[w] = True
                    break
                
                if index == len(next_nodes[v]):
                    passed2[v] = False

    return False


def main():
    N, Q = map(int, input().split())
    next_nodes = [[] for _ in range(N)]
    for i in range(Q):
        A, B = map(int ,input().split())
        next_nodes[A - 1].append((B - 1, i))

    # そもそも閉路が存在するか?
    if not exists_cycle(N, next_nodes, Q - 1):
        print(-1)
        return
    
    low = 0
    high = Q - 1
    while high - low > 1:
        mid = (high + low ) //2
        if exists_cycle(N, next_nodes, mid):
            high = mid
        else:
            low = mid
    if exists_cycle(N, next_nodes, low):
        print(low + 1)
    else:
        print(high + 1)


if __name__ == "__main__":
    main()
0