結果
問題 | No.1813 Magical Stones |
ユーザー |
![]() |
提出日時 | 2024-11-22 14:01:13 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,173 bytes |
コンパイル時間 | 512 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 162,284 KB |
最終ジャッジ日時 | 2024-11-22 14:02:10 |
合計ジャッジ時間 | 23,246 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 8 WA * 32 |
ソースコード
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-=1b-=1es+=[(a,b)]e[a]+=[(b,1)]e[b]+=[(a,0)]class SCC():def __init__(self,n):self.n=nself.e=[[] for i in range(self.n)]self.re=[[] for i in range(self.n)]returndef add_edge(self,s,t):self.e[s]+=[t]self.re[t]+=[s]returndef scc(self):v=[0]*self.ng=[0]*self.no=[]for i in range(self.n):if v[i]==0:q=[i]while len(q)>0:s=q[-1]v[s]=1while g[s]<len(self.e[s]):t=self.e[s][g[s]]if v[t]==0:breakg[s]+=1if g[s]<len(self.e[s]):q+=[t]else:o+=[s]q.pop()c=[-1]*self.np=0for i in o[::-1]:if c[i]==-1:s=ic[s]=pq=[s]for s in q:for t in self.re[s]:if c[t]==-1:c[t]=pq+=[t]p+=1l=[[] for i in range(p)]for i in range(self.n):l[c[i]]+=[i]d=[0]*pfor s in range(self.n):for t in self.e[s]:if c[s]!=c[t]:d[c[t]]+=1ts=[]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]]-=1if 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]*nfor i in range(l):for j in L[i]:c[j]=ido=[0]*ldi=[0]*lfor a,b in es:if c[a]!=c[b]:do[c[a]]+=1di[c[b]]+=1return sum(do[i]==0 or di[i]==0 for i in range(l))c1=0c2=0v=[0]*nfor p in range(n):if v[p]==0:o=[]v[p]=1q=[p]for s in q:o+=[s]for t,_ in e[s]:if v[t]==0:v[t]=1q+=[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+=1c2+=solve(len(o),es2)print(c2-(c1==1))