結果
問題 |
No.679 不思議マーケット
|
ユーザー |
![]() |
提出日時 | 2025-04-09 21:00:55 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,890 bytes |
コンパイル時間 | 174 ms |
コンパイル使用メモリ | 82,344 KB |
実行使用メモリ | 71,976 KB |
最終ジャッジ日時 | 2025-04-09 21:01:43 |
合計ジャッジ時間 | 2,090 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 7 WA * 11 |
ソースコード
import sys from collections import defaultdict def main(): sys.setrecursionlimit(1 << 25) input = sys.stdin.read().split() ptr = 0 n = int(input[ptr]) ptr += 1 m = int(input[ptr]) ptr += 1 conditions = [] conditional_g_set = set() for _ in range(m): g_i = int(input[ptr]) ptr += 1 r_i = int(input[ptr]) ptr += 1 h_list = list(map(int, input[ptr:ptr + r_i])) ptr += r_i conditions.append((g_i, r_i, h_list)) conditional_g_set.add(g_i) if m == 0: print(n) return # Build the dependency graph among conditional goods graph = defaultdict(list) nodes = list(conditional_g_set) for g_i, r_i, h_list in conditions: for h in h_list: if h in conditional_g_set: graph[g_i].append(h) # Implement Tarjan's algorithm for SCC index = 0 indices = {} low = {} on_stack = set() stack = [] sccs = [] def strongconnect(v): nonlocal index indices[v] = index low[v] = index index += 1 stack.append(v) on_stack.add(v) for w in graph[v]: if w not in indices: strongconnect(w) low[v] = min(low[v], low[w]) elif w in on_stack: low[v] = min(low[v], indices[w]) if low[v] == indices[v]: scc = [] while True: w = stack.pop() on_stack.remove(w) scc.append(w) if w == v: break sccs.append(scc) for v in nodes: if v not in indices: strongconnect(v) invalid_count = 0 for scc in sccs: if len(scc) >= 2: invalid_count += len(scc) print(n - invalid_count) if __name__ == "__main__": main()