Submission #654873

#	Time	Username	Problem	Language	Result	Execution time	Memory
654873		inksamurai	Graph (BOI20_graph)	C++17	58 / 100	1086 ms	30344 KiB

Graph

#include <bits/stdc++.h>
#define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3fm6nhZ ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

#define nare {cout<<"NO\n"; exit(0);}

using ld=long double;

const ld eps=1e-6;

signed main(){
_3fm6nhZ;
	cout<<fixed<<setprecision(10);
	int n,m;
	cin>>n>>m;

	vec(vec(pii)) adj(n);
	map<pii,int> mp;
	{
		bool pok=1;
		rep(_,m){
			int u,v,w;
			cin>>u>>v>>w;
			u-=1,v-=1;
			if(u>v) swap(u,v);
			pii e=minmax(u,v);
			if(mp.find(e)!=mp.end() and mp[e]!=w){
				pok=0;
			}
			mp[e]=w;
			adj[u].pb({w,v});
			adj[v].pb({w,u});
		}
		if(!pok) nare;
	}

	vi usd2(n);
	vec(ld) rbe(n);
	auto affine_=[&](int rt,ld x)->ld{ // returns sum of values
		vi way;
		rbe[rt]=x;
		auto rfs=[&](auto self,int v)->void{
			way.pb(v);
			usd2[v]=1;
			for(auto e:adj[v]){
				int u=e.se;
				int w=e.fi;
				if(usd2[u]) continue;
				rbe[u]=(ld)(w)-rbe[v];
				self(self,u);
			}
		};
		rfs(rfs,rt);
		ld res=0;
		for(auto v:way){
			for(auto e:adj[v]){
				int u=e.se;
				int w=e.fi;
				if(u==v) continue;
				// print(rbe[u],)
				if(abs(w-rbe[u]-rbe[v])>eps) nare;
			}
			res+=abs(rbe[v]);
			usd2[v]=0;
		}
		return res;
	};

	auto slv=[&](int rt)->void{
		ld l=-1e9,r=1e9;
		rep(_,300){
			ld ml=(2.0*l+r)/3.0;
			ld mr=(l+2.0*r)/3.0;
			if(affine_(rt,ml)<affine_(rt,mr)){
				r=mr;
			}else{
				l=ml;
			}
		}
	};

	vec(vi) leb(n,vi(2));
	vi usd1(n);
	auto slvcyc=[&](int rt)->void{
		// get way and cycle
		vi way;
		leb[rt][0]=1;
		leb[rt][1]=0;
		auto rfs=[&](auto self,int v)->void{
			way.pb(v);
			usd1[v]=1;
			// print(v,leb[v][0],leb[v][1]);
			for(auto e:adj[v]){
				int u=e.se;
				int w=e.fi;
				if(usd1[u]) continue;
				leb[u][0]=-leb[v][0];
				leb[u][1]=w-leb[v][1];
				self(self,u);
			}
		};
		rfs(rfs,rt);
		int nert=rt;
		ld x;
		bool pok=0;
		for(auto v:way){
			if(pok) break;
			for(auto e:adj[v]){
				int u=e.se;
				int w=e.fi;
				if(u==v){
					pok=1;
					x=(ld)(w)/2.0;
					nert=v;
					break;
				}
				vi now={-leb[v][0],w-leb[v][1]};
				if(leb[u][0]!=now[0]){
					x=(ld)(leb[u][1]-now[1])/(ld)(now[0]-leb[u][0]);
					pok=1;
					break;
				}
			}
		}
		if(!pok){
			slv(nert);
		}else{
			// print("a",x,way[0]);
			// print(x,way[0]);
			affine_(nert,x);
		}
	};

	bool cyc=0;
	vi usd(n);
	auto dfs=[&](auto self,int v,int par)->void{
		usd[v]=1;
		for(auto e:adj[v]){
			int u=e.se;
			if(u==par) continue;
			if(usd[u]){
				cyc=1;
			}else{
				self(self,u,v);
			}
		}
	};
	rep(rt,n){
		if(usd[rt]) continue;
		cyc=0;
		dfs(dfs,rt,-1);
		if(cyc){
			slvcyc(rt);
		}else{
			slv(rt);
		}
	}
	cout<<"YES\n";
	rep(v,n)cout<<rbe[v]<<" ";
}

• Subtask 1: 5 / 5
• Subtask 2: 12 / 12
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 0 / 42