結果
問題 | No.470 Inverse S+T Problem |
ユーザー |
![]() |
提出日時 | 2021-02-09 14:03:35 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 136 ms / 2,000 ms |
コード長 | 5,299 bytes |
コンパイル時間 | 151 ms |
コンパイル使用メモリ | 82,036 KB |
実行使用メモリ | 86,372 KB |
最終ジャッジ日時 | 2024-12-22 14:04:31 |
合計ジャッジ時間 | 3,882 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 27 |
ソースコード
import types_atcoder_code = """# Python port of AtCoder Library.__version__ = '0.0.1'"""atcoder = types.ModuleType('atcoder')exec(_atcoder_code, atcoder.__dict__)_atcoder__scc_code = """import copyimport sysimport typingclass CSR:def __init__(self, n: int, edges: typing.List[typing.Tuple[int, int]]) -> None:self.start = [0] * (n + 1)self.elist = [0] * len(edges)for e in edges:self.start[e[0] + 1] += 1for i in range(1, n + 1):self.start[i] += self.start[i - 1]counter = copy.deepcopy(self.start)for e in edges:self.elist[counter[e[0]]] = e[1]counter[e[0]] += 1class SCCGraph:'''Reference:R. Tarjan,Depth-First Search and Linear Graph Algorithms'''def __init__(self, n: int) -> None:self._n = nself._edges = []def num_vertices(self) -> int:return self._ndef add_edge(self, from_vertex: int, to_vertex: int) -> None:self._edges.append((from_vertex, to_vertex))def scc_ids(self) -> typing.Tuple[int, typing.List[int]]:g = CSR(self._n, self._edges)now_ord = 0group_num = 0visited = []low = [0] * self._norder = [-1] * self._nids = [0] * self._nsys.setrecursionlimit(max(self._n + 1000, sys.getrecursionlimit()))def dfs(v: int) -> None:nonlocal now_ordnonlocal group_numnonlocal visitednonlocal lownonlocal ordernonlocal idslow[v] = now_ordorder[v] = now_ordnow_ord += 1visited.append(v)for i in range(g.start[v], g.start[v + 1]):to = g.elist[i]if order[to] == -1:dfs(to)low[v] = min(low[v], low[to])else:low[v] = min(low[v], order[to])if low[v] == order[v]:while True:u = visited[-1]visited.pop()order[u] = self._nids[u] = group_numif u == v:breakgroup_num += 1for i in range(self._n):if order[i] == -1:dfs(i)for i in range(self._n):ids[i] = group_num - 1 - ids[i]return group_num, idsdef scc(self) -> typing.List[typing.List[int]]:ids = self.scc_ids()group_num = ids[0]counts = [0] * group_numfor x in ids[1]:counts[x] += 1groups = [[] for _ in range(group_num)]for i in range(self._n):groups[ids[1][i]].append(i)return groups"""atcoder._scc = types.ModuleType('atcoder._scc')exec(_atcoder__scc_code, atcoder._scc.__dict__)_atcoder_twosat_code = """import typing# import atcoder._sccclass TwoSAT:'''Reference:B. Aspvall, M. Plass, and R. Tarjan,A Linear-Time Algorithm for Testing the Truth of Certain Quantified BooleanFormulas'''def __init__(self, n: int = 0) -> None:self._n = nself._answer = [False] * nself._scc = atcoder._scc.SCCGraph(2 * n)def add_clause(self, i: int, f: bool, j: int, g: bool) -> None:assert 0 <= i < self._nassert 0 <= j < self._nself._scc.add_edge(2 * i + (0 if f else 1), 2 * j + (1 if g else 0))self._scc.add_edge(2 * j + (0 if g else 1), 2 * i + (1 if f else 0))def satisfiable(self) -> bool:scc_id = self._scc.scc_ids()[1]for i in range(self._n):if scc_id[2 * i] == scc_id[2 * i + 1]:return Falseself._answer[i] = scc_id[2 * i] < scc_id[2 * i + 1]return Truedef answer(self) -> typing.List[bool]:return self._answer"""atcoder.twosat = types.ModuleType('atcoder.twosat')atcoder.twosat.__dict__['atcoder'] = atcoderatcoder.twosat.__dict__['atcoder._scc'] = atcoder._sccexec(_atcoder_twosat_code, atcoder.twosat.__dict__)TwoSAT = atcoder.twosat.TwoSAT# https://atcoder.jp/contests/practice2/tasks/practice2_himport sys# from atcoder.twosat import TwoSATdef main() -> None:N = int(input())S = []for i in range(N):S.append(input())if N>52:print('Impossible')returntwo_sat = TwoSAT(N)for i in range(N):for j in range(i + 1, N):if S[i][:2]==S[j][:2] or S[i][2]==S[j][2]:two_sat.add_clause(i, 0, j, 0)if S[i][:2]==S[j][1:] or S[i][2]==S[j][0]:two_sat.add_clause(i, 0, j, 1)if S[i][1:]==S[j][:2] or S[i][0]==S[j][2]:two_sat.add_clause(i, 1, j, 0)if S[i][1:]==S[j][1:] or S[i][0]==S[j][0]:two_sat.add_clause(i, 1, j, 1)if not two_sat.satisfiable():print("Impossible")else:answer = two_sat.answer()for i in range(N):if answer[i]:print(S[i][0]+S[i][1]+' '+S[i][2])else:print(S[i][0]+' '+S[i][1]+S[i][2])if __name__ == '__main__':main()