結果

問題 No.3104 Simple Graph Problem
ユーザー shobonvip
提出日時 2025-02-01 00:14:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 596 ms / 2,000 ms
コード長 2,614 bytes
コンパイル時間 533 ms
コンパイル使用メモリ 82,460 KB
実行使用メモリ 138,028 KB
最終ジャッジ日時 2025-02-01 00:14:37
合計ジャッジ時間 18,641 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 65
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, m = map(int,input().split())
b = list(map(int,input().split()))
mod = 998244353
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))

# 奇閉路を見つける
tansaku = [0] * n
color = [0] * n
mada = [0]
tansaku[0] = 1
is_bipartite = 1
while mada:
	i = mada.pop()
	for j, c in ikeru[i]:
		if not tansaku[j]:
			tansaku[j] = 1
			color[j] = color[i] ^ 1
			mada.append(j)

cycle_jiku = -1
for i in range(m):
	if color[u[i]] == color[v[i]]:
		cycle_jiku = i
		break

cycle_e = []
cycle_v = []
if cycle_jiku != -1:
	is_bipartite = 0
	x = u[cycle_jiku]
	y = v[cycle_jiku]
	tansaku = [0] * n
	cf = [-1] * n
	tansaku[x] = 1
	mada = [x]
	while mada:
		i = mada.pop()
		for j, c in ikeru[i]:
			if c == cycle_jiku:
				continue
			if color[j] == color[i]:
				continue
			if not tansaku[j]:
				cf[j] = c
				tansaku[j] = 1
				mada.append(j)
	i = y
	cycle_e.append(cycle_jiku)
	cycle_v.append(y)
	while cf[i] != -1:
		cycle_e.append(cf[i])
		i = i ^ u[cf[i]] ^ v[cf[i]]
		cycle_v.append(i)
	cycle_e = cycle_e[::-1]
	cycle_v = cycle_v[::-1]

# 全域木 or 全域なもりグラフをつくる.
new_ikeru = [[] for i in range(n)]
for i in cycle_e:
	new_ikeru[u[i]].append((v[i], i))
	new_ikeru[v[i]].append((u[i], i))

mada = []
tansaku = [0] * n
if is_bipartite:
	tansaku[0] = 1
	mada.append(0)
else:
	for i in cycle_v:
		tansaku[i] = 1
		mada.append(i)

while mada:
	i = mada.pop()
	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))
		mada.append(j)

# 木の部分を削っていく
deg = [0] * n
for i in range(n):
	deg[i] = len(new_ikeru[i])

mada = []
for i in range(n):
	if deg[i] == 1:
		mada.append(i)

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

if not is_bipartite:
	total = 0
	for i in cycle_v:
		total += b[i]
	total %= mod
	total *= pow(2, mod-2, mod)
	total %= mod
	ans[cycle_e[0]] = total
	for i in cycle_v[2::2]:
		ans[cycle_e[0]] -= b[i]
	ans[cycle_e[0]] %= mod
	for i in range(1, len(cycle_e)):
		ans[cycle_e[i]] = b[cycle_v[i]] - ans[cycle_e[i-1]]
		ans[cycle_e[i]] %= mod
	for i in cycle_e:
		b[u[i]] -= ans[i]
		b[v[i]] -= ans[i]
		b[u[i]] %= mod
		b[v[i]] %= mod

for i in range(n):
	if b[i] != 0:
		print(-1)
		exit()

print(*ans)
exit()
0