結果

問題 No.3104 Simple Graph Problem
ユーザー GOTKAKO
提出日時 2025-04-12 01:43:33
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 73 ms / 2,000 ms
コード長 5,753 bytes
コンパイル時間 2,825 ms
コンパイル使用メモリ 224,380 KB
実行使用メモリ 16,768 KB
最終ジャッジ日時 2025-04-12 01:43:45
合計ジャッジ時間 9,607 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 65
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

class UnionFind{
    private:
    vector<int> par,siz;
    public:
    UnionFind(int N){
        par.resize(N,-1);
        siz.resize(N,1);
    }
 
    int root(int x){ //連結成分の代表頂点を返す.
        if(par.at(x) == -1) return x;
        else return par.at(x) = root(par.at(x));
    }
    bool unite(int u, int v){ //u,vを連結する 連結してた->false,した->trueを返す.
        u = root(u),v = root(v);
        if(u == v) return false;
 
        if(siz.at(u) < siz.at(v)) swap(u,v); //Union by size.
        par.at(v) = u;
        siz.at(u) += siz.at(v);
        return true;
    }
    bool issame(int u, int v){ //同じ連結成分ならtrue.
        if(root(u) == root(v)) return true;
        else return false;
    }
    int size(int pos){return siz.at(root(pos));} //posの連結成分の大きさを返す.
};

long long mod = 998244353;
//入力が必ず-mod<a<modの時.
struct mint{
    long long v = 0;
    mint(){} mint(int a){v = a<0?a+mod:a;} mint(long long a){v = a<0?a+mod:a;}
    mint(unsigned long long a){v = a;}
    long long val(){return v;}

    mint &operator=(const mint &b) = default;
    mint operator-() const {return mint(0)-(*this);}
    mint operator+(const mint b){return mint(v)+=b;}
    mint operator-(const mint b){return mint(v)-=b;}
    mint operator*(const mint b){return mint(v)*=b;}
    mint operator/(const mint b){return mint(v)/=b;}

    mint operator+=(const mint b){
        v += b.v; if(v >= mod) v -= mod;
        return *this;
    }
    mint operator-=(const mint b){
        v -= b.v; if(v < 0) v += mod; 
        return *this;
    }   
    mint operator*=(const mint b){v = v*b.v%mod; return *this;}
    mint operator/=(mint b){
        if(b == 0) assert(false);
        int left = mod-2;
        while(left){if(left&1) *this *= b; b *= b; left >>= 1;}
        return *this;
    }

    mint operator++(){*this += 1; return *this;}
    mint operator--(){*this -= 1; return *this;}
    mint operator++(int){*this += 1; return *this;}
    mint operator--(int){*this -= 1; return *this;}
    bool operator==(const mint b){return v == b.v;}
    bool operator!=(const mint b){return v != b.v;}
    bool operator>(const mint b){return v > b.v;}
    bool operator>=(const mint b){return v >= b.v;}
    bool operator<(const mint b){return v < b.v;}
    bool operator<=(const mint b){return v <= b.v;}

    mint pow(long long n){
        mint ret = 1,p = v;
        if(n < 0) p = p.inv(),n = -n;
        while(n){
            if(n&1) ret *= p;
            p *= p; n >>= 1;
        }
        return ret;
    }
    mint inv(){return mint(1)/v;}
};

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

    int N,M; cin >> N >> M;
    vector<mint> A(N);
    for(auto &a : A) cin >> a.v;
    vector<mint> answer(M);
    UnionFind Z(N);
    vector<vector<pair<int,int>>> Graph(N);
    bool first = false;
    vector<tuple<int,int,int>> hold;
    for(int i=0; i<M; i++){
        int u,v; cin >> u >> v;
        u--; v--;
        if(Z.issame(u,v)){hold.push_back({u,v,i}); continue;}
        Graph.at(u).push_back({v,i});
        Graph.at(v).push_back({u,i});
        Z.unite(u,v);
    }

    vector<int> depth(N);
    {
        auto dfs = [&](auto dfs,int pos,int back,int dep) -> void {
            depth.at(pos) = dep;
            for(auto [to,e] : Graph.at(pos)) if(to != back) dfs(dfs,to,pos,dep+1);
        };
        dfs(dfs,0,-1,0);
    }

    bool nibu = true;
    for(auto [u,v,i] : hold){
        int len = (depth.at(u)+depth.at(v)+1);
        if(len%2 == 0) continue;
        nibu = false;
        Graph.at(u).push_back({v,i});
        Graph.at(v).push_back({u,i});
        break;
    }

    if(nibu){
        auto dfs = [&](auto dfs,int pos,int back) -> mint {
            mint left = A.at(pos);
            for(auto [to,e] : Graph.at(pos)){
                if(to == back) continue;
                mint k = dfs(dfs,to,pos);
                left -= k;
                answer.at(e) = k;
            }
            return left;
        };
        if(dfs(dfs,0,-1) != 0) cout << "-1\n";
        else for(int i=0; i<M; i++) cout << answer.at(i).v << (i==M-1?"\n":" ");
        return 0;
    }

    vector<bool> already(N);
    {
        vector<int> D(N);
        for(int i=0; i<N; i++) D.at(i) = Graph.at(i).size();
        queue<int> Q;
        for(int i=0; i<N; i++) if(D.at(i) == 1) Q.push(i);
        while(Q.size()){
            int pos = Q.front(); Q.pop();
            already.at(pos) = true;
            for(auto [to,e] : Graph.at(pos)){
                if(already.at(to)) continue;
                D.at(to)--; answer.at(e) = A.at(pos); A.at(to) -= A.at(pos);
                if(D.at(to) == 1) Q.push(to);
            }
        }
    }
    vector<pair<int,int>> cycle;
    {
        for(int i=0; i<N; i++) if(already.at(i) == false){
            int back = -1,pos = i;
            while(true){
                for(auto [to,e] : Graph.at(pos)){
                    if(back == to || already.at(to)) continue;
                    cycle.push_back({pos,e});
                    back = pos; pos = to;
                    break;
                }
                if(pos == i) break;
            }
            break;
        } 
    }
    int n = cycle.size();
    mint need = 0;
    for(int i=0; i<n; i++){
        auto [pos,e] = cycle.at(i);
        need = A.at(pos)-need;
    }
    need /= 2;
    for(int i=n-1; i>=0; i--){
        auto [pos,e] = cycle.at(i);
        if(i != n-1){
            auto [to,e2] = cycle.at(i+1);
            need = A.at(to)-need;
            answer.at(e) = need;
        }
        else answer.at(e) = need;
    }
    for(int i=0; i<M; i++) cout << answer.at(i).v << (i==M-1?"\n":" ");
}
0