#1190255 (PyPy3) No.3104 Simple Graph Problem

• 問題: No.3104 Simple Graph Problem
• ユーザー: LyricalMaestro
• 提出日時: 2026-09-23 01:21:38
• 言語: PyPy3 (7.3.23 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 3,446 bytes
• コンパイル時間: 65 ms
• コンパイル使用メモリ: 83,164 KB
• 実行使用メモリ: 116,052 KB
• 最終ジャッジ日時: 2026-09-23 01:21:54
• 合計ジャッジ時間: 14,417 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge4_0

ファイルパターン	結果
sample	AC * 3
other	AC * 60 WA * 5

ソースコード

## https://yukicoder.me/problems/no/3104

from collections import deque

MOD = 998244353

def check_is_bigraph(N, M, next_nodes):
    queue = deque()
    queue.append(0)
    passed = [-1] * N
    passed[0]= 0
    prevs = [(-2, -2) for _ in range(N)]
    prevs[0] = (-1, -1)
    illegal_edges = set()
    while len(queue) > 0:
        v = queue.popleft()
        for w, index in next_nodes[v]:
            if passed[w] == -1:
                passed[w] = 1 - passed[v]
                prevs[w] = (v, index)
                queue.append(w)
            else:
                if passed[w] == passed[v]:
                    illegal_edges.add(index)
    return illegal_edges, prevs, passed

def fill_b_to_root(N, M, B, prevs):
    answers = [0] * M
    A = [0] * N
    in_degree = [0] * N
    for i in range(N):
        if prevs[i][0] < 0:
            continue

        v, _ = prevs[i]
        in_degree[v] += 1

    queue = deque()
    for i in range(N):
        if in_degree[i] == 0:
            queue.append(i)

    while len(queue) > 0:
        v = queue.popleft()
        if v != 0:
            b = (B[v] - A[v]) % MOD

            w, index = prevs[v]
            answers[index] += b
            A[v] += b
            A[v] %= MOD
            A[w] += b
            A[w] %= MOD
            in_degree[w] -= 1
            if in_degree[w] == 0:
                queue.append(w)
    return answers, A

def main():
    N, M = map(int, input().split())
    B = list(map(int,input().split()))
    next_nodes = [[  ] for _ in range(N)]
    edges = []
    for i in range(M):
        u, v = map(int, input().split())
        next_nodes[u - 1].append((v - 1, i))
        next_nodes[v - 1].append((u - 1, i))
        edges.append((u - 1, v -1))

    # 2部グラフかどうかの判定
    illegal_edges, prevs, passed =  check_is_bigraph(N, M, next_nodes)
    if len(illegal_edges) == 0:
        # 2部グラフの場合
        values = [0, 0]
        for i in range(N):
            values[passed[i]] += B[i]
            values[passed[i]] %= MOD 
        if values[0] != values[1]:
            print(-1)
            return

        # 2部グラフでの操作
        answer, _ = fill_b_to_root(N, M, B, prevs)
        print(" ".join(map(str, answer)))
    else:
        # 奇数長cycleがある場合は常に対応可能
        answer, A = fill_b_to_root(N, M, B, prevs)
        target_edge_index = list(illegal_edges)[0]

        x = (B[0] - A[0]) % MOD
        y = (x * pow(2, MOD - 2, MOD)) % MOD
        y *= -1
        y %= MOD
        u0, v0 = edges[target_edge_index]
        answer[target_edge_index] += y
        A[u0] += y
        A[v0] += y
        queue = deque()
        queue.append((u0, y))
        queue.append((v0, y))
        while len(queue) > 0:
            v, y0 = queue.popleft()
            w, index = prevs[v]
            answer[index] -= y0
            answer[index] %= MOD
            if w != 0:
                y1 = (-y0) % MOD
                queue.append((w, y1))
        print(" ".join(map(str, answer)))
        
#    if judge(N, M, B, answer, edges):
#        print("OK")
#    else:
#        print("NG")


def judge(N, M, B, answer, edges):
    A = [0] * N
    for i in range(M):
        v, u = edges[i]
        A[v] += answer[i]
        A[v] %= MOD
        A[u] += answer[i]
        A[u] %= MOD

    for i in range(N):
        if A[i] != B[i]:
            return False
    return True

if __name__ == "__main__":
    main()