結果

問題 No.3104 Simple Graph Problem
ユーザー shobonvip
提出日時 2025-02-01 01:41:24
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 1,511 ms / 2,000 ms
コード長 1,351 bytes
コンパイル時間 773 ms
コンパイル使用メモリ 12,416 KB
実行使用メモリ 78,880 KB
最終ジャッジ日時 2025-02-01 01:42:03
合計ジャッジ時間 36,191 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 65
権限があれば一括ダウンロードができます

ソースコード

diff # 

mod = 998244353
n, m = map(int,input().split())
b = list(map(int,input().split()))
u = [0] * m
v = [0] * m
ikeru = [[] for i in range(n)]
for i in range(m):
	u[i], v[i] = map(int,input().split())
	u[i] -= 1
	v[i] -= 1
	ikeru[u[i]].append((v[i], i))
	ikeru[v[i]].append((u[i], i))

new_ikeru = [[] for i in range(n)]
color = [0] * n
tansaku = [0] * n
ans = [0] * m

tansaku[0] = 1
mada = [0]
total = 0
while mada:
	i = mada.pop()
	if color[i] == 0: total += b[i]
	else: total -= b[i]
	for j, c in ikeru[i]:
		if tansaku[j]: continue
		tansaku[j] = 1
		new_ikeru[i].append((j, c))
		new_ikeru[j].append((i, c))
		color[j] = color[i] ^ 1
		mada.append(j)

total %= mod
for i in range(m):
	if color[u[i]] == color[v[i]]:
		inv2 = pow(2, mod-2, mod)
		if color[u[i]] == 0:
			ans[i] = total * inv2 % mod
		else:
			ans[i] = (-total) * inv2 % mod
		b[u[i]] -= ans[i]
		b[v[i]] -= ans[i]
		b[u[i]] %= mod
		b[v[i]] %= mod
		total = 0
		break

if total != 0:
	print(-1)
	exit()

tansaku = [0] * n
mada.append(~0)
mada.append(0)
while mada:
	i = mada.pop()
	if i >= 0:
		for j, c in new_ikeru[i]:
			if tansaku[j] == 0:
				mada.append(~j)
				mada.append(j)
		tansaku[i] = 1
	else:
		i = ~i
		for j, c in new_ikeru[i]:
			if tansaku[j] == 2:
				ans[c] = b[j]
				b[j] -= ans[c]
				b[i] -= ans[c]
				b[j] %= mod
				b[i] %= mod
		tansaku[i] = 2

print(*ans)
0