結果

問題 No.1813 Magical Stones
ユーザー sasa8uyauyasasa8uyauya
提出日時 2024-11-22 14:24:52
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,239 bytes
コンパイル時間 268 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 162,808 KB
最終ジャッジ日時 2024-11-22 14:25:14
合計ジャッジ時間 22,597 ms
ジャッジサーバーID
(参考情報)
judge5 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1 WA * 3
other AC * 2 WA * 38
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

n,m=map(int,input().split())
es=[]
e=[[] for i in range(n)]
for i in range(m):
a,b=map(int,input().split())
a-=1
b-=1
es+=[(a,b)]
e[a]+=[(b,1)]
e[b]+=[(a,0)]
class SCC():
def __init__(self,n):
self.n=n
self.e=[[] for i in range(self.n)]
self.re=[[] for i in range(self.n)]
return
def add_edge(self,s,t):
self.e[s]+=[t]
self.re[t]+=[s]
return
def scc(self):
v=[0]*self.n
g=[0]*self.n
o=[]
for i in range(self.n):
if v[i]==0:
q=[i]
while len(q)>0:
s=q[-1]
v[s]=1
while g[s]<len(self.e[s]):
t=self.e[s][g[s]]
if v[t]==0:
break
g[s]+=1
if g[s]<len(self.e[s]):
q+=[t]
else:
o+=[s]
q.pop()
c=[-1]*self.n
p=0
for i in o[::-1]:
if c[i]==-1:
s=i
c[s]=p
q=[s]
for s in q:
for t in self.re[s]:
if c[t]==-1:
c[t]=p
q+=[t]
p+=1
l=[[] for i in range(p)]
for i in range(self.n):
l[c[i]]+=[i]
d=[0]*p
for s in range(self.n):
for t in self.e[s]:
if c[s]!=c[t]:
d[c[t]]+=1
ts=[]
q=[i for i in range(p) if d[i]==0]
for v in q:
ts+=[v]
for s in l[v]:
for t in self.e[s]:
if c[s]!=c[t]:
d[c[t]]-=1
if d[c[t]]==0:
q+=[c[t]]
return [l[ts[i]] for i in range(p)]
def solve(n,es):
g=SCC(n)
for a,b in es:
g.add_edge(a,b)
L=g.scc()
l=len(L)
c=[0]*n
for i in range(l):
for j in L[i]:
c[j]=i
do=[0]*l
di=[0]*l
for a,b in es:
if c[a]!=c[b]:
do[c[a]]=1
di[c[b]]=1
return max(sum(do[i]==0 and di[i]==1 for i in range(l)),sum(do[i]==1 and di[i]==0 for i in range(l))) if l>1 else 1
c1=0
c2=0
v=[0]*n
for p in range(n):
if v[p]==0:
o=[]
v[p]=1
q=[p]
for s in q:
o+=[s]
for t,_ in e[s]:
if v[t]==0:
v[t]=1
q+=[t]
d={u:i for i,u in enumerate(o)}
es2=[]
for i in o:
for j,f in e[i]:
if f:
es2+=[(d[i],d[j])]
c1+=1
c2+=solve(len(o),es2)
print(c2+c1-(c1==1))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0