結果
問題 | No.2780 The Bottle Imp |
ユーザー |
![]() |
提出日時 | 2024-06-07 21:53:28 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,563 bytes |
コンパイル時間 | 1,275 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 140,256 KB |
最終ジャッジ日時 | 2024-12-27 13:43:39 |
合計ジャッジ時間 | 8,973 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 39 WA * 1 |
ソースコード
class DirectedGraph():def __init__(self, N):self.N = Nself.G = [[] for i in range(N)]self.rG = [[] for i in range(N)]self.order = []self.used1 = [0] * Nself.used2 = [0] * Nself.group = [-1] * Nself.label = 0self.seen = [0] * Nself.Edge = set()def add_edge(self, u, v):#多重辺は排除するif (u, v) not in self.Edge:self.G[u].append(v)self.rG[v].append(u)self.Edge.add((u, v))def dfs(self, s):stack = [~s, s]while stack:u = stack.pop()if u >= 0:if self.used1[u]:continueself.used1[u] = 1for v in self.G[u]:if self.used1[v]:continuestack.append(~v)stack.append(v)else:u = ~uif self.seen[u]:continueself.seen[u]= 1self.order.append(u)def rdfs(self, s, num):stack = [s]while stack:u = stack.pop()if u >= 0:self.used2[u] = 1self.group[u] = numfor v in self.rG[u]:if self.used2[v]:continuestack.append(v)def scc(self):for i in range(self.N):if self.used1[i]:continueif i != 0:print("No")exit()self.dfs(i)for s in reversed(self.order):if self.used2[s]:continueself.rdfs(s, self.label)self.label += 1return self.label, self.groupdef construct(self):nG = [set() for _ in range(self.label)]mem = [[] for i in range(self.label)]for s in range(self.N):now = self.group[s]for u in self.G[s]:if now == self.group[u]:continuenG[now].add(self.group[u])mem[now].append(s)return nG, memN = int(input())G = DirectedGraph(N)for i in range(N):A = list(map(int, input().split()))M = A.pop(0)for j in range(M):G.add_edge(i, A[j]-1)G.scc()nG, mem = G.construct()if 0 not in mem[0]:print("No")exit()for v in nG:if len(v) >= 2:print("No")exit()print("Yes")