結果
問題 | No.2780 The Bottle Imp |
ユーザー |
👑 |
提出日時 | 2024-06-07 21:41:12 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 266 ms / 2,000 ms |
コード長 | 2,875 bytes |
コンパイル時間 | 374 ms |
コンパイル使用メモリ | 82,472 KB |
実行使用メモリ | 113,260 KB |
最終ジャッジ日時 | 2024-12-27 13:36:47 |
合計ジャッジ時間 | 8,190 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
class SCC:def __init__(self, n, edges=None):self.n = nif edges is None:self.edges = []else:self.edges = edgesdef add_edge(self, u, v):self.edges.append((u, v))def read_edges(self, m, indexed=1):for _ in range(m):u, v = map(int, input().split())u -= indexedv -= indexedself.add_edge(u, v)def build(self):start = [0] * (self.n + 1)elist = [0] * len(self.edges)for u, _ in self.edges:start[u + 1] += 1for i in range(1, self.n + 1):start[i] += start[i - 1]counter = start[:]for u, v in self.edges:elist[counter[u]] = vcounter[u] += 1now_ord = 0group_num = 0visited = []low = [0] * self.nord = [-1] * self.nids = [0] * self.nbpos = [-1] * self.ndef dfs(v):nonlocal now_ord, group_numvisited.append(v)stack = [~v, v]while stack:pos = stack.pop()if pos >= 0:if ord[pos] == -1:low[pos] = ord[pos] = now_ordnow_ord += 1visited.append(pos)for i in range(start[pos], start[pos + 1]):to = elist[i]if ord[to] == -1:stack.append(~to)stack.append(to)bpos[to] = poselse:low[pos] = min(low[pos], ord[to])else:pos = ~posif low[pos] == ord[pos]:while 1:u = visited.pop()ord[u] = self.nids[u] = group_numif u == pos:breakgroup_num += 1if bpos[pos] != -1:low[bpos[pos]] = min(low[bpos[pos]], low[pos])for i in range(self.n):if ord[i] == -1:dfs(i)for i in range(self.n):ids[i] = group_num - 1 - ids[i]return group_num, idsn = int(input())G = SCC(n)edges = [[] for _ in range(n)]for i in range(n):m, *A = map(int, input().split())for a in A:a -= 1G.add_edge(i, a)edges[i].append(a)l, ids = G.build()if ids[0] != 0:print("No")exit()ok = [False] * (l - 1)for i in range(n):for j in edges[i]:if ids[i] + 1 == ids[j]:ok[ids[i]] = Trueif all(ok):print("Yes")else:print("No")