結果
問題 | No.1813 Magical Stones |
ユーザー |
|
提出日時 | 2022-01-15 15:01:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 568 ms / 2,000 ms |
コード長 | 1,405 bytes |
コンパイル時間 | 320 ms |
コンパイル使用メモリ | 82,164 KB |
実行使用メモリ | 114,788 KB |
最終ジャッジ日時 | 2024-11-21 16:04:40 |
合計ジャッジ時間 | 13,149 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
import sysint1 = lambda x: int(x) - 1# input = lambda: sys.stdin.buffer.readline()input = lambda: sys.stdin.readline().rstrip()ii = lambda: int(input())i1 = lambda: int1(input())mi = lambda: map(int, input().split())mi1 = lambda: map(int1, input().split())li = lambda: list(mi())li1 = lambda: list(mi1())lli = lambda n: [li() for _ in range(n)]INF = float("inf")mod = int(1e9 + 7)# mod = 998244353n, m = mi()g = [list() for i in range(n)]rg = [list() for i in range(n)]for i in range(m):a, b = mi1()g[a].append(b)rg[b].append(a)st = []order = []used = [False] * nfor i in range(n):st.append(i)while st:cur = st.pop()if cur < 0:order.append(-cur - 1)continueif used[cur]:continueused[cur] = Truest.append(-cur - 1)for to in g[cur]:st.append(to)cmp = [-1] * nc = 0for v in order[::-1]:if cmp[v] != -1:continuest.append(v)while st:cur = st.pop()if cmp[cur] != -1:continuecmp[cur] = cfor to in rg[cur]:st.append(to)c += 1IN = [0] * cOUT = [0] * cfor cur in range(n):for to in g[cur]:if cmp[to] != cmp[cur]:OUT[cmp[cur]] += 1IN[cmp[to]] += 1if c == 1:print(0)else:print(max(IN.count(0), OUT.count(0)))