結果
問題 | No.3104 Simple Graph Problem |
ユーザー |
![]() |
提出日時 | 2025-04-11 22:36:12 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 105 ms / 2,000 ms |
コード長 | 6,436 bytes |
コンパイル時間 | 7,839 ms |
コンパイル使用メモリ | 337,412 KB |
実行使用メモリ | 16,972 KB |
最終ジャッジ日時 | 2025-04-11 22:36:29 |
合計ジャッジ時間 | 14,957 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 65 |
ソースコード
#include <bits/stdc++.h> // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #include <atcoder/all> using namespace std; using namespace atcoder; using ll=long long; using LL=__int128; using ld=long double; using uint=unsigned int; using ull=unsigned long long; using pii=pair<int,int>; using pll=pair<ll,ll>; template<typename T> using vc=vector<T>; template<typename T> using vvc=vector<vc<T>>; template<typename T> using vvvc=vector<vvc<T>>; using vi=vc<int>; using vvi=vvc<int>; using vd=vc<ld>; using vvd=vvc<ld>; using vl=vc<ll>; using vvl=vvc<ll>; using vs=vc<string>; using vp=vc<pll>; using vvp=vvc<pll>; #define overload3(_1,_2,_3,name,...) name #define rep1(n) for(ll _=0;_<ll(n);_++) #define rep2(i,n) for(ll i=0;i<ll(n);i++) #define rep3(i,a,b) for(ll i=ll(a);i<ll(b);i++) #define rep(...) overload3(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__) #define rrep1(n) for(ll _=ll(n);_--;) #define rrep2(i,n) for(ll i=ll(n);i--;) #define rrep3(i,a,b) for(ll i=ll(b);i-->ll(a);) #define rrep(...) overload3(__VA_ARGS__,rrep3,rrep2,rrep1)(__VA_ARGS__) #define ALL(a) (a).begin(),(a).end() #define RALL(a) (a).rbegin(),(a).rend() template<int m> ostream& operator<<(ostream& os,static_modint<m> v){ os<<v.val(); return os; } istream& operator>>(istream& is,__int128& v){ string s; is>>s; v=0; rep(i,s.size())if(isdigit(s[i])) v=v*10+s[i]-'0'; if(s[0]=='-') v*=-1; return is; } ostream& operator<<(ostream& os,__int128 v){ ostream::sentry s(os); if(s){ __uint128_t t=v<0?-v:v; char buf[128]; char* d=end(buf); do{ d--; *d="0123456789"[t%10]; t/=10; }while(t); if(v<0){ d--; *d='-'; } int len=end(buf)-d; if(os.rdbuf()->sputn(d,len)!=len) os.setstate(ios_base::badbit); } return os; } template<typename S,typename T> ostream& operator<<(ostream& os,pair<S,T> a){ os<<a.first<<' '<<a.second; return os; } template<typename T> ostream& operator<<(ostream& os,vector<T> a){ if(a.empty()) return os; os<<a[0]; rep(i,1,a.size()) os<<' '<<a[i]; return os; } template<typename T> ostream& operator<<(ostream& os,vector<vector<T>> a){ if(a.empty()) return os; os<<a[0]; rep(i,1,a.size()) os<<endl<<a[i]; return os; } void output(auto x){cout<<x<<endl;} template<typename T> void output(vector<T> a,bool next_line=0){ if(next_line){ for(auto x:a) output(x); } else cout<<a<<endl; } void debug(auto ...vs){ ((cout<<vs<<", "),...)<<endl; } void syosu(int x=15){cout<<fixed<<setprecision(x);} void YN(bool x){cout<<(x?"Yes":"No")<<endl;} void chmin(auto &x,auto y){if(x>y) x=y;} void chmax(auto &x,auto y){if(x<y) x=y;} template<typename T> void read(vector<T> &a,int n,int off=0){ a=vector<T>(n); for(auto &i:a){ cin>>i; i-=off; } } void read(vs &a,int n){ a=vs(n); for(auto &i:a) cin>>i; } template<typename T> void read(vector<pair<T,T>> &a,int n,int off=0){ a=vector<pair<T,T>>(n); for(auto &[x,y]:a){ cin>>x>>y; x-=off,y-=off; } } template<typename T> void read(vector<vector<T>> &a,int n,int m,int off=0){ a=vector<vector<T>>(n,vector<T>(m)); for(auto &i:a) for(auto &j:i){ cin>>j; j-=off; } } template<typename T> void readGraph(vector<vector<T>> &g,int n,int m,bool rv=1,int off=1){ g=vector<vector<T>>(n); for(int i=0;i<m;i++){ T u,v; cin>>u>>v; u-=off,v-=off; g[u].emplace_back(v); if(rv) g[v].emplace_back(u); } } template<typename T> void readGraph(vector<vector<pair<T,T>>> &g,int n,int m,bool id=0,bool rv=1,int off=1){ g=vector<vector<pair<T,T>>>(n); for(int i=0;i<m;i++){ if(id){ T u,v; cin>>u>>v; u-=off,v-=off; g[u].emplace_back(v,i); if(rv) g[v].emplace_back(u,i); } else{ T u,v,w; cin>>u>>v>>w; u-=off,v-=off; g[u].emplace_back(v,w); if(rv) g[v].emplace_back(u,w); } } } string toBinary(ll x,ll n,bool rev=0){ assert(0<=x&&x<1LL<<n); string s(n,'0'); for(int i=0;i<n;i++) if(x&1LL<<i) s[n-i-1]='1'; if(rev) reverse(s.begin(),s.end()); return s; } constexpr ll inf=1<<30; constexpr ll INF=1ll<<60; const ld pi=acosl(-1); constexpr ld eps=1e-9; //constexpr ll mod=1e9+7; constexpr ll mod=998244353; constexpr int dx[9]={-1,0,1,0,1,1,-1,-1,0}; constexpr int dy[9]={0,1,0,-1,1,-1,1,-1,0}; using mint=static_modint<mod>; using vm=vc<mint>; using vvm=vvc<mint>; void main2(); int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); ll q=1; // cin>>q; while(q--) main2(); } void main2(){ ll n,m; cin>>n>>m; vm a(n); rep(i,n){ ll x; cin>>x; a[i]=x; } const vm a_=a; vp ed; read(ed,m,1); dsu uft(2*n); for(auto [u,v]:ed){ uft.merge(u,v+n); uft.merge(u+n,v); } vm rs(m); if(uft.same(0,n)){ dsu uft2(n); dsu uft3(2*n); vvp g(n); vl deg(n); bool flag=true; rep(i,m){ auto [u,v]=ed[i]; if(!uft2.same(u,v)){ uft2.merge(u,v); uft3.merge(u,v+n); uft3.merge(u+n,v); g[u].emplace_back(v,i); g[v].emplace_back(u,i); deg[u]++,deg[v]++; } else if(flag&&uft3.same(u,v)){ flag=false; uft2.merge(u,v); g[u].emplace_back(v,i); g[v].emplace_back(u,i); deg[u]++,deg[v]++; } } queue<ll> q; rep(i,n)if(deg[i]==1) q.emplace(i); while(!q.empty()){ ll v=q.front();q.pop(); for(auto [u,i]:g[v])if(deg[u]){ deg[u]--,deg[v]--; if(deg[u]==1) q.emplace(u); rs[i]=a[v]; a[u]-=rs[i]; } } vl vs; rep(i,n)if(deg[i]==2){ ll v=i,pre=v; do{ vs.emplace_back(v); for(auto [u,_]:g[v])if(deg[u]&&u!=pre){ pre=v,v=u; break; } }while(v!=i); break; } mint tp=0; ll sz=vs.size(); rep(i,sz){ ll v=vs[i]; tp+=a[v]*(i==0||i%2==1?1:-1); } rep(i,sz){ ll v=vs[i],nv=vs[(i+1)%sz]; for(auto [u,id]:g[v])if(u==nv){ rs[id]=tp/2; } tp=-tp+2*a[nv]; } } else{ mint sm=0; rep(i,n) sm+=(uft.same(i,0)?a[i]:-a[i]); if(sm==0){ dsu uft2(n); vvp g(n); vl deg(n); rep(i,m){ auto [u,v]=ed[i]; if(!uft2.same(u,v)){ uft2.merge(u,v); g[u].emplace_back(v,i); g[v].emplace_back(u,i); deg[u]++,deg[v]++; } } queue<ll> q; rep(i,n)if(deg[i]==1) q.emplace(i); rep(n-1){ assert(!q.empty()); ll v=q.front();q.pop(); for(auto [u,i]:g[v])if(deg[u]){ deg[u]--,deg[v]--; if(deg[u]==1) q.emplace(u); rs[i]=a[v]; a[u]-=rs[i]; } } } else{ rs.clear(); } } if(rs.empty()) output(-1); else{ output(rs); vm b(n); rep(i,m){ auto [u,v]=ed[i]; b[u]+=rs[i]; b[v]+=rs[i]; } assert(a_==b); } }