結果

問題 No.1865 Make Cycle
ユーザー LyricalMaestroLyricalMaestro
提出日時 2024-08-03 01:36:04
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,413 bytes
コンパイル時間 522 ms
コンパイル使用メモリ 82,292 KB
実行使用メモリ 99,892 KB
最終ジャッジ日時 2024-08-03 01:36:14
合計ジャッジ時間 7,741 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 AC 381 ms
99,892 KB
testcase_05 AC 198 ms
92,044 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 180 ms
91,312 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 360 ms
96,004 KB
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 169 ms
89,580 KB
testcase_18 AC 178 ms
91,960 KB
testcase_19 WA -
testcase_20 AC 36 ms
56,240 KB
testcase_21 AC 38 ms
53,692 KB
testcase_22 AC 36 ms
54,364 KB
testcase_23 AC 39 ms
54,440 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

from collections import deque

def solve(N, next_nodes, border_q):
    queue = deque()
    passed = [-1] * N
    p_id = 0    
    for s_i in range(N):
        if passed[s_i] == -1:
            queue.append(s_i)
            passed[s_i] = p_id
            while len(queue) > 0:
                v = queue.popleft()
                for w, q in next_nodes[v].items():
                    if q > border_q:
                        continue

                    if w == s_i:
                        return True

                    if passed[w] == -1:
                        passed[w] = p_id
                        queue.append(w)

            p_id += 1
    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())
        a -= 1
        b -= 1
        if b not in next_nodes[a]:
            next_nodes[a][b] = i

    # 全て繋げた状態で    
    ans = solve(N, next_nodes, Q - 1)
    if not ans:
        print(-1)
        return
    
    low = 0
    high = Q - 1
    while high - low > 1:
        mid = (high + low) // 2
        if solve(N, next_nodes, mid):
            high = mid
        else:
            low = mid
    if solve(N, next_nodes, low):
        print(low + 1)
    else:
        print(high + 1)

        



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