結果
問題 | No.3104 Simple Graph Problem |
ユーザー |
![]() |
提出日時 | 2025-04-11 23:11:56 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 483 ms / 2,000 ms |
コード長 | 2,644 bytes |
コンパイル時間 | 4,569 ms |
コンパイル使用メモリ | 260,372 KB |
実行使用メモリ | 28,400 KB |
最終ジャッジ日時 | 2025-04-11 23:12:17 |
合計ジャッジ時間 | 18,688 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 65 |
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 4000000000000000001LL mint dfs(int cv,int pv,vector<vector<int>> &E,vector<mint> &res,vector<mint> &b, vector<int> &v,vector<int> &u){ mint ret = 0; rep(i,E[cv].size()){ int ii = E[cv][i]; int to = cv ^ u[ii] ^ v[ii];; if(to==pv)continue; mint r = dfs(to,cv,E,res,b,u,v); res[ii] = b[to] - r; ret += res[ii]; } return ret; } vector<mint> get(int n,vector<int> u,vector<int> v,vector<mint> b){ vector<vector<int>> E(n); rep(i,n-1){ E[u[i]].push_back(i); E[v[i]].push_back(i); } vector<mint> res(n-1); dfs(0,-1,E,res,b,u,v); return res; } unsigned long xor128() { static unsigned long x=123456789, y=362436069, z=521288629, w=88675123; unsigned long t=(x^(x<<11)); x=y; y=z; z=w; return (w=(w^(w>>19))^(t^(t>>8))); } int main(){ int n,m; cin>>n>>m; vector<mint> b(n); rep(i,n){ int bb; cin>>bb; b[i] = bb; } vector<int> u(m),v(m); vector<int> idx; dsu D(n); dsu D2(n*2); int ii = -1; rep(i,m){ cin>>u[i]>>v[i]; u[i]--,v[i]--; } rep(_,30){ vector<int> is(m); rep(i,m){ is[i] = i; swap(is[i],is[xor128()%(i+1)]); } dsu D(n),D2(n*2); idx.clear(); rep(i,m){ int ci = is[i]; if(!D.same(u[ci],v[ci])){ D.merge(u[ci],v[ci]); D2.merge(u[ci],v[ci]+n); D2.merge(u[ci]+n,v[ci]); idx.push_back(ci); } else{ D2.merge(u[ci],v[ci]+n); D2.merge(u[ci]+n,v[ci]); if(D2.same(u[ci],u[ci]+n) || D2.same(v[ci],v[ci]+n)){ if(ii==-1)ii = ci; } } } if(ii!=-1)break; } vector<int> u2,v2; rep(i,idx.size()){ u2.push_back(u[idx[i]]); v2.push_back(v[idx[i]]); } vector<mint> res = get(n,u2,v2,b); { vector<mint> cur(n); vector<mint> ans(m); rep(i,res.size()){ ans[idx[i]] = res[i]; cur[u[idx[i]]] += res[i]; cur[v[idx[i]]] += res[i]; } if(cur == b){ rep(i,m){ if(i!=0)cout<<' '; cout<<ans[i].val(); } cout<<endl; return 0; } if(ii==-1){ cout<<-1<<endl; return 0; } mint over = (cur[0]-b[0]); over /= 2; rep(_,2){ auto bb = b; bb[u[ii]] -= over; bb[v[ii]] -= over; ans.assign(m,0); res = get(n,u2,v2,bb); cur.assign(n,0); rep(i,res.size()){ ans[idx[i]] = res[i]; cur[u[idx[i]]] += res[i]; cur[v[idx[i]]] += res[i]; } ans[ii] = over; if(cur==bb){ rep(i,m){ if(i!=0)cout<<' '; cout<<ans[i].val(); } cout<<endl; return 0; } over *= -1; } assert(false); } return 0; }