結果
問題 | No.2236 Lights Out On Simple Graph |
ユーザー | Shirotsume |
提出日時 | 2023-03-03 23:00:32 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 3,582 ms / 4,000 ms |
コード長 | 5,916 bytes |
コンパイル時間 | 154 ms |
コンパイル使用メモリ | 82,188 KB |
実行使用メモリ | 78,296 KB |
最終ジャッジ日時 | 2024-09-18 00:14:23 |
合計ジャッジ時間 | 170,214 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3,543 ms
77,216 KB |
testcase_01 | AC | 39 ms
55,764 KB |
testcase_02 | AC | 3,543 ms
77,400 KB |
testcase_03 | AC | 69 ms
76,488 KB |
testcase_04 | AC | 67 ms
76,412 KB |
testcase_05 | AC | 46 ms
64,220 KB |
testcase_06 | AC | 3,568 ms
77,824 KB |
testcase_07 | AC | 3,574 ms
77,732 KB |
testcase_08 | AC | 42 ms
56,248 KB |
testcase_09 | AC | 3,545 ms
77,360 KB |
testcase_10 | AC | 3,565 ms
77,944 KB |
testcase_11 | AC | 3,560 ms
77,648 KB |
testcase_12 | AC | 3,568 ms
77,660 KB |
testcase_13 | AC | 3,562 ms
77,852 KB |
testcase_14 | AC | 3,568 ms
78,296 KB |
testcase_15 | AC | 3,556 ms
77,616 KB |
testcase_16 | AC | 3,555 ms
77,616 KB |
testcase_17 | AC | 3,566 ms
77,880 KB |
testcase_18 | AC | 3,553 ms
77,876 KB |
testcase_19 | AC | 3,567 ms
77,556 KB |
testcase_20 | AC | 61 ms
74,432 KB |
testcase_21 | AC | 64 ms
75,996 KB |
testcase_22 | AC | 3,572 ms
77,812 KB |
testcase_23 | AC | 3,575 ms
77,452 KB |
testcase_24 | AC | 3,566 ms
77,760 KB |
testcase_25 | AC | 3,563 ms
77,896 KB |
testcase_26 | AC | 3,568 ms
77,560 KB |
testcase_27 | AC | 3,568 ms
77,584 KB |
testcase_28 | AC | 3,565 ms
77,584 KB |
testcase_29 | AC | 61 ms
75,920 KB |
testcase_30 | AC | 3,566 ms
78,052 KB |
testcase_31 | AC | 3,565 ms
77,856 KB |
testcase_32 | AC | 3,570 ms
77,948 KB |
testcase_33 | AC | 3,568 ms
77,944 KB |
testcase_34 | AC | 3,567 ms
77,816 KB |
testcase_35 | AC | 3,572 ms
78,108 KB |
testcase_36 | AC | 3,582 ms
78,268 KB |
testcase_37 | AC | 3,573 ms
78,024 KB |
testcase_38 | AC | 3,569 ms
78,292 KB |
testcase_39 | AC | 3,570 ms
77,748 KB |
testcase_40 | AC | 62 ms
73,544 KB |
testcase_41 | AC | 59 ms
71,268 KB |
testcase_42 | AC | 3,579 ms
77,648 KB |
testcase_43 | AC | 3,561 ms
77,392 KB |
testcase_44 | AC | 3,567 ms
77,508 KB |
testcase_45 | AC | 3,572 ms
77,696 KB |
testcase_46 | AC | 67 ms
76,428 KB |
testcase_47 | AC | 3,577 ms
78,076 KB |
testcase_48 | AC | 64 ms
76,412 KB |
testcase_49 | AC | 61 ms
76,476 KB |
testcase_50 | AC | 3,552 ms
77,908 KB |
testcase_51 | AC | 3,571 ms
77,748 KB |
testcase_52 | AC | 3,564 ms
77,908 KB |
testcase_53 | AC | 53 ms
67,848 KB |
testcase_54 | AC | 3,569 ms
77,944 KB |
testcase_55 | AC | 3,574 ms
78,208 KB |
testcase_56 | AC | 3,580 ms
78,068 KB |
testcase_57 | AC | 3,568 ms
78,196 KB |
testcase_58 | AC | 3,568 ms
77,960 KB |
testcase_59 | AC | 3,570 ms
78,016 KB |
ソースコード
import sys from collections import deque, Counter input = lambda: sys.stdin.readline().rstrip() ii = lambda: int(input()) mi = lambda: map(int, input().split()) li = lambda: list(mi()) inf = 2 ** 63 - 1 mod = 2 class matrix(): r = 1 c = 1 A = None mod = 2 def __init__(self, r, c, mod = 2): self.r = r self.c = c self.A = [[0] * self.c for _ in range(self.r)] if mod is not None: self.mod = mod def makeone(r = 1): A = matrix(r, r, mod) for i in range(r): A[i, i] = 1 return A def __getitem__(self, key): rnow, cnow = key return self.A[rnow][cnow] def __setitem__(self, key, value): rnow, cnow = key self.A[rnow][cnow] = value def __add__(self, other): assert self.r == other.r and self.c == other.c ret = matrix(self.r, self.c) for i in range(self.r): for j in range(self.c): ret[i, j] = self[i, j] + other[i, j] ret[i, j] %= self.mod return ret def __sub__(self, other): assert self.r == other.r and self.c == other.c ret = matrix(self.r, self.c) for i in range(self.r): for j in range(self.c): ret[i, j] = self[i, j] - other[i, j] ret[i, j] %= self.mod return ret def __mul__(self, other): assert self.c == other.r ret = matrix(self.r, other.c) for i in range(self.r): for j in range(self.c): for k in range(other.c): ret[i, k] += self[i, j] * other[j, k] ret[i, k] %= self.mod return ret def augment(self, other): assert self.r == other.r X = matrix(self.r, self.c + other.c, mod = self.mod) for i in range(self.r): for j in range(self.c): X[i, j] = self[i, j] for j in range(other.c): X[i, j + self.c] = other[i, j] return X def diminish(self, c): X = [] for i in range(self.r): X.append((self.A[i][:c])) return matrix(self.r, c, mod = self.mod, A = X) def hakidashi(self): for i in range(self.c): for j in range(i + 1, self.r): if self.A[j][i] != 0: for k in range(self.c): self.A[j][k], self.A[i][k] = self.A[i][k], self.A[j][k] break for i in range(self.r): for j in range(self.c): if self[i, j] != 0: break else: continue K = pow(self[i, j], self.mod - 2, self.mod) for to in range(self.c): self[i, to] *= K self[i, to] %= self.mod for i2 in range(self.r): if i == i2: continue time = self[i2, j] for j2 in range(self.c): self[i2, j2] -= time * self[i, j2] self[i2, j2] %= self.mod return self def inv(self): assert self.c == self.r one = matrix.makeone(r = self.r) new = self.augment(one) new.hakidashi() for i in range(self.r): for j in range(self.c): if i == j: if new[i, j] != 1: return 0, new else: if new[i, j] != 0: return 0, new X = matrix(self.r, self.c) for i in range(self.r): for j in range(self.c): X[i, j] = new[i, j + self.c] return 1, X def lineareq(self, b): assert self.r == b.r assert b.c == 1 Y = self.augment(b) Y = Y.hakidashi() B = [[0] * self.c for _ in range(self.c)] ans = [0] * self.c flag = [0] * self.c for i in range(self.r): j = 0 while j < self.c and Y[i, j] == 0: j += 1 if j == self.c: if Y[i, -1] != 0: return None, None continue flag[j] = 1 ans[j] = Y[i, -1] for k in range(j + 1, self.c): if Y[i, k] % self.mod != 0: B[k][j] = (-Y[i, k])% self.mod flag[k] = -1 for i in range(self.c): if flag[i] != 1: B[i][i] = 1 B=[B[i] for i in range(self.c) if flag[i] != 1] return ans,B def print(self): for v in self.A: print(*v) import sys input = lambda: sys.stdin.readline().rstrip() ii = lambda: int(input()) mi = lambda: map(int, input().split()) li = lambda: list(mi()) INF = 2 ** 63 - 1 mod = 2 n, m = mi() EDGE = [[v - 1 for v in li()] for _ in range(m)] graph = [[] for _ in range(n)] for u, v in EDGE: graph[u].append(v) graph[v].append(u) c = li() A = matrix(n, m) B = matrix(n, 1) for i, V in enumerate(EDGE): u, v = V A[u, i] = 1 A[v, i] = 1 for i in range(n): if c[i] == 1: B[i, 0] = 1 X, Y = A.lineareq(B) if X is None: print(-1) exit() YY = matrix(len(Y), m) for i in range(len(Y)): for j in range(m): YY[i, j] = Y[i][j] YY = YY.hakidashi() for i in range(len(Y)): for j in range(m): Y[i][j] = YY[i, j] ans = X.count(1) if Y: import random import time t1 = time.time() while time.time() - t1 < 3.5: p = random.randint(0, len(Y) - 1) for i in range(m): X[i] ^= Y[p][i] if ans > X.count(1): ans = min(ans, X.count(1)) elif random.random() > 0.9: for i in range(m): X[i] ^= Y[p][i] print(ans)