結果
問題 | No.1865 Make Cycle |
ユーザー | puzneko |
提出日時 | 2022-04-07 22:52:03 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 2,685 bytes |
コンパイル時間 | 248 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 564,752 KB |
最終ジャッジ日時 | 2024-11-28 02:15:59 |
合計ジャッジ時間 | 60,245 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2,530 ms
272,028 KB |
testcase_01 | AC | 2,013 ms
492,580 KB |
testcase_02 | AC | 2,452 ms
271,532 KB |
testcase_03 | AC | 552 ms
123,528 KB |
testcase_04 | AC | 1,575 ms
274,232 KB |
testcase_05 | MLE | - |
testcase_06 | TLE | - |
testcase_07 | AC | 2,771 ms
268,212 KB |
testcase_08 | TLE | - |
testcase_09 | AC | 2,611 ms
278,060 KB |
testcase_10 | TLE | - |
testcase_11 | AC | 2,903 ms
278,984 KB |
testcase_12 | AC | 2,182 ms
268,932 KB |
testcase_13 | AC | 2,553 ms
248,512 KB |
testcase_14 | AC | 2,463 ms
266,140 KB |
testcase_15 | TLE | - |
testcase_16 | TLE | - |
testcase_17 | AC | 2,213 ms
266,572 KB |
testcase_18 | AC | 2,906 ms
281,048 KB |
testcase_19 | TLE | - |
testcase_20 | AC | 37 ms
52,872 KB |
testcase_21 | AC | 39 ms
52,864 KB |
testcase_22 | AC | 37 ms
52,736 KB |
testcase_23 | AC | 35 ms
335,932 KB |
ソースコード
import math from sys import stdin n, q, *indata = map(int, stdin.read().split()) offset = 0 m = int(math.floor(math.sqrt(q))) g = [[] for i in range(n+1)] repeat = (q-1) // m + 1 cyclecheck = -1 for i in range(repeat): g2 = [[] for i in range(n+1)] for j in range(m): ind = i * m + j if ind >= q: break else: s, t = indata[ind*2]-1,indata[ind*2+1]-1 g2[s].append(t) check = [0 for j in range(n)] for j in range(n): if check[j] == 0: que = [(j,0)] while que: now, inout = que.pop() if inout == 0: if check[now] == 0: que.append((now,1)) check[now] = 1 for k in g[now]: if check[k] == 1: cyclecheck = i break elif check[k] == 0: que.append((k,0)) for k in g2[now]: if check[k] == 1: cyclecheck = i break elif check[k] == 0: que.append((k,0)) if cyclecheck != -1: break else: check[now] = 2 if cyclecheck != -1: break if cyclecheck != -1: break else: for j in range(m): ind = i * m + j if ind >= q: break else: s, t = indata[ind*2]-1,indata[ind*2+1]-1 g[s].append(t) if cyclecheck == -1: print("{}".format(-1)) exit() for i in range(m): ind = cyclecheck * m + i if ind >= q: break else: s, t = indata[ind*2]-1,indata[ind*2+1]-1 g[s].append(t) check = [0 for j in range(n)] for j in range(n): if check[j] == 0: que = [(j,0)] while que: now, inout = que.pop() if inout == 0: if check[now] == 0: que.append((now,1)) check[now] = 1 for k in g[now]: if check[k] == 1: ans = cyclecheck * m + i + 1 print("{}".format(ans)) exit() elif check[k] == 0: que.append((k,0)) else: check[now] = 2