結果
問題 | No.3104 Simple Graph Problem |
ユーザー |
![]() |
提出日時 | 2025-02-01 01:41:11 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 451 ms / 2,000 ms |
コード長 | 1,351 bytes |
コンパイル時間 | 1,089 ms |
コンパイル使用メモリ | 82,060 KB |
実行使用メモリ | 123,592 KB |
最終ジャッジ日時 | 2025-02-01 01:41:31 |
合計ジャッジ時間 | 17,169 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 65 |
ソースコード
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)