結果
問題 | No.1078 I love Matrix Construction |
ユーザー | neterukun |
提出日時 | 2020-06-12 23:00:35 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,875 bytes |
コンパイル時間 | 459 ms |
コンパイル使用メモリ | 87,284 KB |
実行使用メモリ | 134,920 KB |
最終ジャッジ日時 | 2023-09-06 11:09:44 |
合計ジャッジ時間 | 11,043 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 74 ms
71,604 KB |
testcase_01 | AC | 75 ms
71,428 KB |
testcase_02 | AC | 215 ms
86,056 KB |
testcase_03 | AC | 307 ms
99,524 KB |
testcase_04 | AC | 364 ms
108,120 KB |
testcase_05 | WA | - |
testcase_06 | AC | 209 ms
86,088 KB |
testcase_07 | AC | 176 ms
80,368 KB |
testcase_08 | AC | 328 ms
103,132 KB |
testcase_09 | WA | - |
testcase_10 | AC | 552 ms
134,920 KB |
testcase_11 | AC | 390 ms
110,156 KB |
testcase_12 | AC | 498 ms
125,040 KB |
testcase_13 | AC | 521 ms
131,612 KB |
testcase_14 | AC | 405 ms
114,456 KB |
testcase_15 | AC | 501 ms
128,616 KB |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | AC | 197 ms
83,944 KB |
testcase_19 | AC | 245 ms
91,932 KB |
testcase_20 | AC | 247 ms
92,016 KB |
testcase_21 | AC | 112 ms
77,856 KB |
ソースコード
def is_bipartite(graph, s): """頂点sを含むgraphが二部グラフかどうかを判定する""" n = len(graph) stack = [s] used[s] = 0 while stack: v = stack.pop() for nxt_v in graph[v]: if used[nxt_v] == -1: used[nxt_v] = used[v] ^ 1 stack.append(nxt_v) elif used[nxt_v] ^ used[v] == 0: return False return True def make_bipartite(graph, root): n = len(graph) stack = [root] col[root] = 0 while stack: v = stack.pop() for nxt_v in graph[v]: if col[nxt_v] != -1: continue col[nxt_v] = col[v] ^ 1 stack.append(nxt_v) def to_ind(i, j, lr): if lr == 0: ans = i * n + j + n ** 2 else: ans = i * n + j return ans n = int(input()) s = list(map(int, input().split())) t = list(map(int, input().split())) u = list(map(int, input().split())) graph = [[] for i in range(2 * n * n)] for i in range(n): for j in range(n): si = s[i] - 1 ti = t[i] - 1 ul, ur = u[i] % 2, u[i] // 2 graph[to_ind(si, j, ul)].append(to_ind(j, ti, ur)) graph[to_ind(j, ti, ur)].append(to_ind(si, j, ul)) for i in range(n ** 2): graph[i].append(i + n ** 2) graph[i + n ** 2].append(i) flag = True used = [-1] * (2 * n * n) for i in range(2 * n * n): if used[i] != -1: continue flag &= is_bipartite(graph, i) if not flag: print(-1) exit() used = [False] * (2 * n * n) col = [-1] * (2 * n * n) for i in range(2 * n * n): if col[i] != -1: continue make_bipartite(graph, i) ans = [[0] * n for i in range(n)] for i in range(n): for j in range(n): if col[to_ind(i, j, 0)] == 1: ans[i][j] = 1 else: ans[i][j] = 0 for res in ans: print(*res)