結果

問題 No.3104 Simple Graph Problem
ユーザー tassei903
提出日時 2025-04-11 22:52:47
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,103 bytes
コンパイル時間 3,336 ms
コンパイル使用メモリ 295,620 KB
実行使用メモリ 15,944 KB
最終ジャッジ日時 2025-04-11 22:53:03
合計ジャッジ時間 9,485 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 23 WA * 8 TLE * 1 -- * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll MOD = 998244353;

struct UnionFind {
    vector<int> parent;
    UnionFind(int n) : parent(n, -1) {}

    int find(int x) {
        if (parent[x] < 0) return x;
        return parent[x] = find(parent[x]);
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    void unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        if (parent[x] > parent[y]) swap(x, y);
        parent[x] += parent[y];
        parent[y] = x;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<ll> b(n);
    for (int i = 0; i < n; ++i) cin >> b[i];

    UnionFind uf(n * 2);
    vector<vector<pair<int, int>>> g(n);
    bool flag = false;
    int cnt = 0;

    vector<pair<int, int>> edges(m);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        edges[i] = {u, v};
        if (!uf.same(u, v) && !uf.same(u, v + n)) {
            uf.unite(u, v + n);
            uf.unite(u + n, v);
            g[u].emplace_back(v, i);
            g[v].emplace_back(u, i);
            cnt++;
        } else if (uf.same(u, v) && !flag) {
            flag = true;
            g[u].emplace_back(v, i);
            g[v].emplace_back(u, i);
            cnt++;
        }
    }

    vector<ll> ans(m);
    if (cnt == n - 1) {
        vector<int> dp(n, -1), p(n, -1), pi(n, -1), seen(n);
        vector<int> et, q = {0};
        seen[0] = 1;

        while (!q.empty()) {
            int x = q.back(); q.pop_back();
            et.push_back(x);
            for (auto [y, j] : g[x]) {
                if (!seen[y]) {
                    seen[y] = 1;
                    p[y] = x;
                    pi[y] = j;
                    q.push_back(y);
                }
            }
        }

        for (int i = (int)et.size() - 1; i > 0; --i) {
            int v = et[i];
            int u = p[v];
            int j = pi[v];
            ans[j] = b[v] % MOD;
            b[u] -= b[v];
            b[u] = (b[u] % MOD + MOD) % MOD;
            b[v] = 0;
        }

        if (b[0] == 0) {
            for (ll x : ans) cout << x << " ";
            cout << "\n";
        } else {
            cout << -1 << "\n";
        }

    } else {
        vector<int> deg(n), seen(n);
        for (int i = 0; i < n; ++i) deg[i] = g[i].size();
        deque<int> q;
        for (int i = 0; i < n; ++i)
            if (deg[i] == 1) q.push_back(i);

        while (!q.empty()) {
            int x = q.front(); q.pop_front();
            seen[x] = 1;
            for (auto [z, j] : g[x]) {
                if (seen[z]) continue;
                int y = z, i = j;
                ans[i] = b[x];
                b[y] -= b[x];
                b[y] = (b[y] % MOD + MOD) % MOD;
                b[x] = 0;
                deg[y]--;
                if (deg[y] == 1) q.push_back(y);
                break;
            }
        }

        int X = -1;
        for (int i = 0; i < n; ++i) {
            if (deg[i] == 2) {
                X = i;
                break;
            }
        }

        vector<int> P = {X}, PI;
        int Y = X, pre = -1;

        while (true) {
            for (auto [z, j] : g[Y]) {
                if (z != pre) {
                    P.push_back(z);
                    PI.push_back(j);
                    pre = Y;
                    Y = z;
                    break;
                }
            }
            if (Y == X) break;
        }

        ll Z = 0;
        for (int v : P) Z = (Z + b[v]) % MOD;
        Z = Z * ((MOD + 1) / 2) % MOD;

        ll a[2] = {0, 0};
        for (int i = 0; i < (int)P.size() / 2 * 2; ++i)
            a[i % 2] = (a[i % 2] + b[P[i]]) % MOD;

        int sz = P.size();
        for (int i = 0; i < sz; ++i) {
            ans[PI[i]] = (Z - a[(i % 2) ^ 1] + MOD) % MOD;
            a[i % 2] = (a[i % 2] - b[P[i]] + b[P[(i - 1 + sz) % sz]] + MOD) % MOD;
        }

        for (ll x : ans) cout << x << " ";
        cout << "\n";
    }

    return 0;
}
0