oj.uz

Submission #654869

# Submission time Handle Problem Language Result Execution time Memory
654869 2022-11-01T19:50:03 Z inksamurai Graph (BOI20_graph) C++17
0 / 100
 1 ms 212 KB 
#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;
	};

	vec(vi) leb(n,vi(2));
	vi usd1(n);
	auto slvcyc=[&](int rt)->void{
		// get way and cycle
		vi way;
		vi cyc;
		auto rfs=[&](auto self,int v,int par)->void{
			way.pb(v);
			usd1[v]=1;
			for(auto e:adj[v]){
				int u=e.se;
				if(u==par) continue;
				if(usd1[u]){
					if(!sz(cyc)){
						vi delay;
						per(i,sz(way)){
							cyc.pb(way[i]);
							if(way[i]==u) break;
						}
					}
				}else{
					self(self,u,v);
				}
			}
			way.pop_back();
		};
		rfs(rfs,rt,-1);
		ld x;
		if(sz(cyc)==1){ // self edge
			x=mp[pii(cyc[0],cyc[0])];
		}else{
			leb[cyc[0]][0]=1;
			leb[cyc[0]][1]=0;
			rng(i,1,sz(cyc)){
				int v=cyc[i];
				int u=cyc[i-1];
				int w=mp[minmax(v,u)]; // don't forget about pencakes
				leb[v][0]=-leb[u][0];
				leb[v][1]=w-leb[u][1];
			}
			int cof=leb[sz(cyc)-1][0];
			int ad=leb[cyc[sz(cyc)-1]][1];
			cof++;
			ad=mp[minmax(cyc[0],cyc[sz(cyc)-1])]-ad;
			if(cof==0) nare;
			x=(ld)(ad)/(ld)(cof);
		}
		affine_(cyc[0],x);
	};

	auto slv=[&](int rt)->void{
		ld l=-1e9,r=1e9;
		rep(_,100){
			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;
			}
		}
	};

	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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB answer = YES
2 Correct 1 ms 212 KB answer = YES
3 Correct 0 ms 212 KB answer = YES
4 Correct 1 ms 212 KB answer = NO
5 Correct 1 ms 212 KB answer = YES
6 Correct 0 ms 212 KB answer = YES
7 Correct 1 ms 212 KB answer = YES
8 Correct 0 ms 212 KB answer = YES
9 Correct 1 ms 212 KB answer = NO
10 Incorrect 0 ms 212 KB jury has the better answer: jans = YES, pans = NO
11 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB answer = YES
2 Correct 1 ms 212 KB answer = YES
3 Correct 0 ms 212 KB answer = YES
4 Correct 1 ms 212 KB answer = NO
5 Correct 1 ms 212 KB answer = YES
6 Correct 0 ms 212 KB answer = YES
7 Correct 1 ms 212 KB answer = YES
8 Correct 0 ms 212 KB answer = YES
9 Correct 1 ms 212 KB answer = NO
10 Incorrect 0 ms 212 KB jury has the better answer: jans = YES, pans = NO
11 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB answer = YES
2 Correct 1 ms 212 KB answer = YES
3 Correct 0 ms 212 KB answer = YES
4 Correct 1 ms 212 KB answer = NO
5 Correct 1 ms 212 KB answer = YES
6 Correct 0 ms 212 KB answer = YES
7 Correct 1 ms 212 KB answer = YES
8 Correct 0 ms 212 KB answer = YES
9 Correct 1 ms 212 KB answer = NO
10 Incorrect 0 ms 212 KB jury has the better answer: jans = YES, pans = NO
11 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB answer = YES
2 Correct 1 ms 212 KB answer = YES
3 Correct 0 ms 212 KB answer = YES
4 Correct 1 ms 212 KB answer = NO
5 Correct 1 ms 212 KB answer = YES
6 Correct 0 ms 212 KB answer = YES
7 Correct 1 ms 212 KB answer = YES
8 Correct 0 ms 212 KB answer = YES
9 Correct 1 ms 212 KB answer = NO
10 Incorrect 0 ms 212 KB jury has the better answer: jans = YES, pans = NO
11 Halted 0 ms 0 KB -

Subtask #5
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB answer = YES
2 Correct 1 ms 212 KB answer = YES
3 Correct 0 ms 212 KB answer = YES
4 Correct 1 ms 212 KB answer = NO
5 Correct 1 ms 212 KB answer = YES
6 Correct 0 ms 212 KB answer = YES
7 Correct 1 ms 212 KB answer = YES
8 Correct 0 ms 212 KB answer = YES
9 Correct 1 ms 212 KB answer = NO
10 Incorrect 0 ms 212 KB jury has the better answer: jans = YES, pans = NO
11 Halted 0 ms 0 KB -