結果
問題 | No.1865 Make Cycle |
ユーザー |
|
提出日時 | 2022-03-11 12:36:50 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,957 bytes |
コンパイル時間 | 524 ms |
コンパイル使用メモリ | 82,688 KB |
実行使用メモリ | 198,624 KB |
最終ジャッジ日時 | 2024-09-15 12:41:07 |
合計ジャッジ時間 | 32,889 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 19 RE * 1 |
ソースコード
import sysinput = lambda :sys.stdin.readline()[:-1]ni = lambda :int(input())na = lambda :list(map(int,input().split()))yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES")no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO")######################################################################## 強連結成分分解(SCC): グラフGに対するSCCを行う# 入力: <N>: 頂点サイズ, <G>: 順方向の有向グラフ, <RG>: 逆方向の有向グラフ# 出力: (<ラベル数>, <各頂点のラベル番号>)def scc(N, G, RG, y):order = []used = [0]*Ngroup = [None]*Ndef dfs(s):used[s] = 1for t,x in G[s]:if x > y:continueif not used[t]:dfs(t)order.append(s)def rdfs(s, col):group[s] = colused[s] = 1for t, x in RG[s]:if x > y:continueif not used[t]:rdfs(t, col)for i in range(N):if not used[i]:dfs(i)used = [0]*Nlabel = 0for s in reversed(order):if not used[s]:rdfs(s, label)label += 1return label, group# 縮約後のグラフを構築def construct(N, G, label, group):G0 = [set() for i in range(label)]GP = [[] for i in range(label)]for v in range(N):lbs = group[v]for w in G[v]:lbt = group[w]if lbs == lbt:continueG0[lbs].add(lbt)GP[lbs].append(v)return G0, GPn,q = na()g = [[] for i in range(n)]rg = [[] for i in range(n)]for j in range(q):a,b = na()a-=1b-=1g[a].append((b,j))rg[b].append((a, j))ok = qng = -1while (ok-ng)>1:d = (ok+ng)//2if scc(n,g,rg,d)[0]<n:ok = delse:ng = dif ok == q:print(-1)else:print(ok+1)