結果
問題 | No.1194 Replace |
ユーザー | rlangevin |
提出日時 | 2024-02-03 16:39:58 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,876 ms / 2,000 ms |
コード長 | 3,302 bytes |
コンパイル時間 | 374 ms |
コンパイル使用メモリ | 82,472 KB |
実行使用メモリ | 337,792 KB |
最終ジャッジ日時 | 2024-09-28 10:53:13 |
合計ジャッジ時間 | 31,263 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,449 ms
258,680 KB |
testcase_01 | AC | 1,189 ms
261,336 KB |
testcase_02 | AC | 964 ms
224,460 KB |
testcase_03 | AC | 854 ms
201,300 KB |
testcase_04 | AC | 1,198 ms
262,088 KB |
testcase_05 | AC | 1,132 ms
246,640 KB |
testcase_06 | AC | 1,072 ms
238,740 KB |
testcase_07 | AC | 1,717 ms
316,780 KB |
testcase_08 | AC | 1,771 ms
316,804 KB |
testcase_09 | AC | 1,876 ms
317,592 KB |
testcase_10 | AC | 1,713 ms
334,944 KB |
testcase_11 | AC | 1,753 ms
335,832 KB |
testcase_12 | AC | 1,752 ms
337,792 KB |
testcase_13 | AC | 901 ms
191,732 KB |
testcase_14 | AC | 780 ms
169,008 KB |
testcase_15 | AC | 753 ms
176,048 KB |
testcase_16 | AC | 889 ms
190,104 KB |
testcase_17 | AC | 723 ms
166,232 KB |
testcase_18 | AC | 645 ms
154,568 KB |
testcase_19 | AC | 916 ms
196,680 KB |
testcase_20 | AC | 42 ms
54,400 KB |
testcase_21 | AC | 42 ms
54,272 KB |
testcase_22 | AC | 42 ms
54,144 KB |
testcase_23 | AC | 384 ms
122,284 KB |
testcase_24 | AC | 214 ms
95,020 KB |
testcase_25 | AC | 135 ms
80,744 KB |
testcase_26 | AC | 380 ms
117,676 KB |
testcase_27 | AC | 140 ms
82,688 KB |
testcase_28 | AC | 250 ms
93,556 KB |
testcase_29 | AC | 125 ms
78,912 KB |
ソースコード
import sys input = sys.stdin.readline from bisect import * from copy import deepcopy def compress(lst): ''' B: lstを座圧したリスト idx_to_val: indexから元の値を取得するリスト val_to_idx: 元の値からindexを取得する辞書 ''' B = [] val_to_idx = {} idx_to_val = deepcopy(lst) idx_to_val = list(set(idx_to_val)) idx_to_val.sort() for i in range(len(lst)): ind = bisect_left(idx_to_val, lst[i]) B.append(ind) for i in range(len(B)): val_to_idx[lst[i]] = B[i] return B, idx_to_val, val_to_idx class DirectedGraph(): def __init__(self, N): self.N = N self.G = [[] for i in range(N)] self.rG = [[] for i in range(N)] self.order = [] self.used1 = [0] * N self.used2 = [0] * N self.group = [-1] * N self.label = 0 self.seen = [0] * N self.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]: continue self.used1[u] = 1 for v in self.G[u]: if self.used1[v]: continue stack.append(~v) stack.append(v) else: u = ~u if self.seen[u]: continue self.seen[u]= 1 self.order.append(u) def rdfs(self, s, num): stack = [s] while stack: u = stack.pop() if u >= 0: self.used2[u] = 1 self.group[u] = num for v in self.rG[u]: if self.used2[v]: continue stack.append(v) def scc(self): for i in range(self.N): if self.used1[i]: continue self.dfs(i) for s in reversed(self.order): if self.used2[s]: continue self.rdfs(s, self.label) self.label += 1 return self.label, self.group def 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]: continue nG[now].add(self.group[u]) mem[now].append(s) return nG, mem N, M = map(int, input().split()) B, C = [0] * M, [0] * M for i in range(M): B[i], C[i] = map(int, input().split()) D, itov, _ = compress(B + C) B, C = D[:M], D[M:] K = max(D) + 1 G = DirectedGraph(K) for i in range(M): G.add_edge(C[i], B[i]) L, _ = G.scc() nG, mem = G.construct() ans = N * (N + 1) // 2 dp = [0] * L for i in range(L): dp[i] = max(mem[i]) for i in range(L): for u in nG[i]: dp[u] = max(dp[u], dp[i]) for m in mem[i]: ans += max(0, itov[dp[i]] - itov[m]) print(ans)