結果
| 問題 |
No.2236 Lights Out On Simple Graph
|
| コンテスト | |
| ユーザー |
lam6er
|
| 提出日時 | 2025-03-31 17:30:04 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 3,078 bytes |
| コンパイル時間 | 242 ms |
| コンパイル使用メモリ | 82,816 KB |
| 実行使用メモリ | 76,652 KB |
| 最終ジャッジ日時 | 2025-03-31 17:30:51 |
| 合計ジャッジ時間 | 6,694 ms |
|
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 8 TLE * 1 -- * 48 |
ソースコード
def main():
import sys
input = sys.stdin.read
data = input().split()
index = 0
N = int(data[index])
index += 1
M = int(data[index])
index += 1
edges = []
for _ in range(M):
a = int(data[index]) - 1 # convert to 0-based
index += 1
b = int(data[index]) - 1
index += 1
edges.append((a, b))
c = list(map(int, data[index:index + N]))
index += N
# Create equations: each row is (mask, target)
rows = []
for i in range(N):
mask = 0
for j in range(M):
a, b = edges[j]
if i == a or i == b:
mask |= (1 << j)
target = c[i]
rows.append((mask, target))
rank = 0
pivot_cols = [] # list of pivot columns (variable indices)
n = N
# Gaussian elimination
for col in range(M): # columns are processed from 0 to M-1 (left to right)
pivot_row = -1
for r in range(rank, n):
if (rows[r][0] >> col) & 1:
pivot_row = r
break
if pivot_row == -1:
continue
# Swap current row (rank) with pivot_row
rows[rank], rows[pivot_row] = rows[pivot_row], rows[rank]
current_row = rows[rank]
# Eliminate this column in other rows
for r in range(n):
if r != rank and ( (rows[r][0] >> col) & 1 ):
# XOR with current_row
rows[r] = (rows[r][0] ^ current_row[0], rows[r][1] ^ current_row[1])
pivot_cols.append(col)
rank += 1
# Check for inconsistency (0 = 1)
for r in range(rank, n):
if rows[r][1] != 0:
print(-1)
return
# If no equations, check if all targets are zero (trivial solution)
if rank == 0:
for t in [row[1] for row in rows]:
if t != 0:
print(-1)
return
print(0)
return
# Now, find solutions
pivot_set = set(pivot_cols)
free_vars = [col for col in range(M) if col not in pivot_set]
k = len(free_vars)
min_ops = float('inf')
from itertools import product
# Generate all possible combinations of free variables (0/1)
for bits in product([0, 1], repeat=k):
x = [0] * M
# Assign values to free variables
for i in range(k):
x[free_vars[i]] = bits[i]
# Compute pivot variables from highest to lowest column (reverse order of pivot_cols)
for r in reversed(range(rank)):
col = pivot_cols[r]
mask, target = rows[r]
sum_val = 0
for j in range(M):
if j == col:
continue
if (mask >> j) & 1:
sum_val ^= x[j]
x[col] = (target ^ sum_val) & 1
# Calculate the number of operations
total = sum(x)
if total < min_ops:
min_ops = total
if min_ops != float('inf'):
print(min_ops)
else:
print(-1)
if __name__ == "__main__":
main()
lam6er