#1066632 (C++23) No.3104 Simple Graph Problem

提出ソース

結果

問題	No.3104 Simple Graph Problem
コンテスト
ユーザー	Tourmaline
提出日時	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

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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);
	}
}

yukicoder

結果

ソースコード