結果
問題 | No.241 出席番号(1) |
ユーザー | tktk_snsn |
提出日時 | 2021-01-23 14:56:03 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 121 ms / 2,000 ms |
コード長 | 3,705 bytes |
コンパイル時間 | 269 ms |
コンパイル使用メモリ | 87,140 KB |
実行使用メモリ | 78,696 KB |
最終ジャッジ日時 | 2023-08-29 01:50:29 |
合計ジャッジ時間 | 6,276 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 90 ms
71,952 KB |
testcase_01 | AC | 93 ms
76,596 KB |
testcase_02 | AC | 103 ms
77,156 KB |
testcase_03 | AC | 85 ms
71,788 KB |
testcase_04 | AC | 99 ms
77,448 KB |
testcase_05 | AC | 89 ms
71,792 KB |
testcase_06 | AC | 90 ms
71,772 KB |
testcase_07 | AC | 87 ms
71,960 KB |
testcase_08 | AC | 86 ms
71,924 KB |
testcase_09 | AC | 89 ms
72,004 KB |
testcase_10 | AC | 85 ms
71,472 KB |
testcase_11 | AC | 88 ms
71,660 KB |
testcase_12 | AC | 90 ms
71,792 KB |
testcase_13 | AC | 96 ms
76,664 KB |
testcase_14 | AC | 118 ms
77,996 KB |
testcase_15 | AC | 117 ms
78,620 KB |
testcase_16 | AC | 90 ms
71,828 KB |
testcase_17 | AC | 89 ms
71,768 KB |
testcase_18 | AC | 91 ms
71,500 KB |
testcase_19 | AC | 89 ms
71,792 KB |
testcase_20 | AC | 88 ms
71,580 KB |
testcase_21 | AC | 89 ms
71,876 KB |
testcase_22 | AC | 88 ms
71,904 KB |
testcase_23 | AC | 113 ms
77,816 KB |
testcase_24 | AC | 112 ms
78,080 KB |
testcase_25 | AC | 121 ms
78,696 KB |
testcase_26 | AC | 115 ms
77,820 KB |
testcase_27 | AC | 108 ms
77,824 KB |
testcase_28 | AC | 118 ms
78,568 KB |
testcase_29 | AC | 117 ms
78,244 KB |
testcase_30 | AC | 116 ms
78,004 KB |
testcase_31 | AC | 118 ms
78,000 KB |
ソースコード
from collections import deque class MF_graph(object): def __init__(self, n): self.n = n self.g = [[] for _ in range(n)] # to, rev, cap self.pos = [] def add_edge(self, frm, to, cap): """ frmからtoへ容量cap, 流量0の辺を追加, 何番目の辺かを返す""" m = len(self.pos) self.pos.append((frm, len(self.g[frm]))) self.g[frm].append([to, len(self.g[to]), cap]) self.g[to].append([frm, len(self.g[frm]) - 1, 0]) return m def __get_edge(self, i): e_to, e_rev, e_cap = self.g[self.pos[i][0]][self.pos[i][1]] re_to, _, re_cap = self.g[e_to][e_rev] # from, to, cap, flow return (re_to, e_to, e_cap + re_cap, re_cap) def edges(self): """ 辺の情報を返す(frm, to, cap, flow) """ m = len(self.pos) for i in range(m): yield self.__get_edge(i) def change_edge(self, i, new_cap, new_flow): """ i番目に追加された辺の容量,流量をnew_cap, new_flowに変更する """ f, s = self.pos[i] rf, rs, _ = self.g[f][s] self.g[f][s][2] = new_cap - new_flow self.g[rf][rs][2] = new_flow return def __dfs(self, s, v, up): if v == s: return up res = 0 level_v = self.level[v] for i in range(self.iter[v], len(self.g[v])): u_to, u_rev, _ = self.g[v][i] if level_v <= self.level[u_to] or self.g[u_to][u_rev][2] == 0: continue d = self.__dfs(s, u_to, min(up - res, self.g[u_to][u_rev][2])) if d <= 0: continue self.g[v][i][2] += d self.g[u_to][u_rev][2] -= d res += d if res == up: break return res def flow(self, s, t, flow_limit=10**18): """ sからtへflow_limitだけ流す。流せた量を返す """ self.iter = [0] * self.n flow = 0 while flow < flow_limit: self.level = [-1] * self.n self.level[s] = 0 que = deque([s]) while que: v = que.popleft() for u_to, _, u_cap in self.g[v]: if u_cap == 0 or self.level[u_to] >= 0: continue self.level[u_to] = self.level[v] + 1 if u_to == t: break que.append(u_to) if self.level[t] == -1: break self.iter = [0] * self.n while flow < flow_limit: f = self.__dfs(s, t, flow_limit - flow) if not f: break flow += f return flow def min_cut(self, s): """ 最小カットを返す。sから到達可能だとTrue """ visited = [False] * self.n que = deque([s]) while que: v = que.popleft() visited[v] = True for u_to, _, u_cap in self.g[v]: if u_cap and (not visited[u_to]): visited[u_to] = True que.append(u_to) return visited N = int(input()) G = MF_graph(2 * N + 2) source = 2 * N sink = source + 1 for i in range(N): s = int(input()) G.add_edge(source, i, 1) G.add_edge(i+N, sink, 1) for j in range(N): if s == j: continue G.add_edge(i, N + j, 1) if G.flow(source, sink) != N: print(-1) exit() ans = [-1] * N for frm, to, _, f in G.edges(): if frm == source: continue if to == sink: continue if f: ans[frm] = to - N print(*ans, sep="\n")