結果
| 問題 |
No.1865 Make Cycle
|
| コンテスト | |
| ユーザー |
👑  Kazun
|
| 提出日時 | 2022-03-05 00:09:54 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,979 ms / 3,000 ms |
| コード長 | 7,171 bytes |
| コンパイル時間 | 255 ms |
| コンパイル使用メモリ | 82,304 KB |
| 実行使用メモリ | 320,384 KB |
| 最終ジャッジ日時 | 2024-07-19 20:24:50 |
| 合計ジャッジ時間 | 25,442 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 20 |
ソースコード
def General_Binary_Increase_Search_Integer(L,R,cond,default=None):
"""条件式が単調増加であるとき, 整数上で二部探索を行う.
L: 解の下限
R: 解の上限
cond: 条件(1変数関数, 広義単調増加を満たす)
default: Lで条件を満たさないときの返り値
"""
if not(cond(R)): return default
if cond(L): return L
R+=1
while R-L>1:
C=L+(R-L)//2
if cond(C): R=C
else: L=C
return R
class Digraph:
"""重み[なし]有向グラフを生成する.
"""
#入力定義
def __init__(self, N):
""" N 頂点の空グラフを生成する. """
self.N=N
self.arc_number=0
self.adjacent_out=[set() for v in range(N)]#出近傍(vが始点)
self.adjacent_in=[set() for v in range(N)] #入近傍(vが終点)
#辺の追加
def add_arc(self, source, target):
if target not in self.adjacent_out[source]:
self.adjacent_out[source].add(target)
self.adjacent_in[target].add(source)
self.arc_number+=1
#辺を除く
def remove_arc(self, source, target):
if target in self.adjacent_out[source]:
self.adjacent_out[source].discard(target)
self.adjacent_in[target].discard(source)
self.arc_number-=1
def reset_vertex(self, u):
""" 頂点 u に接続している辺を全て消す."""
X=self.adjacent_out[u].copy()
for v in X:
self.remove_arc(u,v)
X=self.adjacent_in[u].copy()
for w in X:
self.remove_arc(w,u)
#Walkの追加
def add_walk(self,*walk):
N=len(walk)
for k in range(N-1):
self.add_arc(walk[k],walk[k+1])
#Cycleの追加
def add_cycle(self,*cycle):
self.add_walk(*cycle)
self.add_arc(cycle[-1],cycle[0])
#グラフに辺が存在するか否か
def arc_exist(self, source, target):
return target in self.adjacent_out[source]
#近傍
def neighbohood(self,v):
"""vの出近傍, 入近傍を出力する.
Input:
v:頂点
Output:
(出近傍, 入近傍)
"""
return (self.adjacent_out[v],self.adjacent_in[v])
#出次数
def out_degree(self,v):
return len(self.adjacent_out[v])
#入次数
def in_degree(self,v):
return len(self.adjacent_in[v])
#次数
def degree(self,v):
return (self.out_degree(v),self.in_degree(v))
#相対次数
def relative_degree(self,v):
return self.out_degree(v)-self.in_degree(v)
#頂点数
def vertex_count(self):
return self.vertex_number
#辺数
def arc_count(self):
return self.arc_number
#頂点vに到達可能な頂点
def reachable_to(self,v):
from collections import deque
T=[0]*self.N; T[v]=1
Q=deque([v])
while Q:
x=Q.pop()
for y in self.adjacent_in[x]:
if not T[y]:
T[y]=1
Q.append(y)
return [x for x in range(self.N) if T[x]]
#頂点vから到達可能な頂点
def reachable_from(self,v):
from collections import deque
T=[0]*self.N; T[v]=1
Q=deque([v])
while Q:
x=Q.pop()
for y in self.adjacent_out[x]:
if not T[y]:
T[y]=1
Q.append(y)
return [x for x in range(self.N) if T[x]]
#頂点 u,v の距離を求める.
def distance(self,u,v):
if u==v:
return 0
from collections import deque
inf=float("inf")
adj_out=self.adjacent_out
T=[inf]*self.N; T[u]=0
Q=deque([u])
while Q:
w=Q.popleft()
for x in adj_out[w]:
if T[x]==inf:
T[x]=T[w]+1
Q.append(x)
if x==v:
return T[x]
return inf
#ある1点からの距離
def distance_all(self,u):
""" 頂点 u からの距離を求める."""
from collections import deque
inf=float("inf")
adj_out=self.adjacent_out
T=[inf]*self.N; T[u]=0
Q=deque([u])
while Q:
w=Q.popleft()
for x in adj_out[w]:
if T[x]==inf:
T[x]=T[w]+1
Q.append(x)
return T
def shortest_path(self,u,v, dist=False):
""" u から v への最短路を求める (存在しない場合は None).
dist: False → shortest_path のみ, True → (dist, shortest_path)"""
if u==v:
if dist:
return (0,[u])
else:
return [u]
from collections import deque
inf=float("inf")
adj_in=self.adjacent_in
T=[-1]*self.N
Q=deque([v]); T[v]=v
while Q:
w=Q.popleft()
for x in adj_in[w]:
if T[x]==-1:
T[x]=w
Q.append(x)
if x==u:
P=[u]
a=u
while a!=v:
a=T[a]
P.append(a)
return (len(P)-1,P)
return (inf,None)
#深いコピー
def deepcopy(self):
from copy import deepcopy
D=Digraph(self.N)
D.arc_number=self.arc_number
D.adjacent_out=deepcopy(self.adjacent_out)
D.adjacent_in=deepcopy(self.adjacent_in)
return D
#Cycleを見つける.
#参考元:https://judge.yosupo.jp/submission/23992
def Find_Cycle(D):
from collections import deque
in_deg=[D.in_degree(v) for v in range(D.N)]
adj_out=D.adjacent_out
Q=deque([v for v in range(D.N) if in_deg[v]==0])
while Q:
v=Q.popleft()
for w in adj_out[v]:
in_deg[w]-=1
if in_deg[w]==0:
Q.append(w)
for v in range(D.N):
P=[]
if in_deg[v]==0:
continue
Q=deque([v])
prev=[-1]*D.N
while Q:
x=Q.popleft()
for y in adj_out[x]:
if y==v:
prev[v]=x
break
if prev[y]!=-1:
continue
prev[y]=x
Q.append(y)
else:
continue
break
else:
continue
P=[v]
x=v
while prev[x]!=v:
x=prev[x]
P.append(x)
break
if P:
return P[::-1]
else:
return None
#==================================================
def check(q):
D=Digraph(N+1)
for a,b in A[:q]:
D.add_arc(a,b)
return bool(Find_Cycle(D))
#==================================================
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
A=[None]*Q
for q in range(Q):
a,b=map(int,input().split())
A[q]=(a,b)
print(General_Binary_Increase_Search_Integer(1,Q,check,-1))