oj.uz

Submission #654878

# Submission time Handle Problem Language Result Execution time Memory
654878 2022-11-01T20:24:32 Z inksamurai Graph (BOI20_graph) C++17
5 / 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;
	};

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

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB answer = YES
2 Correct 0 ms 212 KB answer = YES
3 Correct 0 ms 212 KB answer = YES
4 Correct 0 ms 212 KB answer = NO
5 Correct 0 ms 212 KB answer = YES
6 Correct 1 ms 212 KB answer = YES
7 Correct 0 ms 212 KB answer = YES
8 Correct 0 ms 212 KB answer = YES
9 Correct 0 ms 212 KB answer = NO
10 Correct 0 ms 212 KB answer = YES
11 Correct 0 ms 212 KB answer = YES
12 Correct 0 ms 212 KB answer = NO
13 Correct 1 ms 212 KB answer = YES
14 Correct 1 ms 212 KB answer = YES
15 Correct 1 ms 212 KB answer = YES
16 Correct 1 ms 212 KB answer = YES
17 Correct 0 ms 212 KB answer = YES
18 Correct 0 ms 212 KB answer = YES
19 Correct 0 ms 212 KB answer = YES
20 Correct 0 ms 212 KB answer = YES
21 Correct 0 ms 212 KB answer = YES
22 Correct 0 ms 212 KB answer = NO
23 Correct 0 ms 212 KB answer = NO

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB answer = YES
2 Correct 0 ms 212 KB answer = YES
3 Correct 0 ms 212 KB answer = YES
4 Correct 0 ms 212 KB answer = NO
5 Correct 0 ms 212 KB answer = YES
6 Correct 1 ms 212 KB answer = YES
7 Correct 0 ms 212 KB answer = YES
8 Correct 0 ms 212 KB answer = YES
9 Correct 0 ms 212 KB answer = NO
10 Correct 0 ms 212 KB answer = YES
11 Correct 0 ms 212 KB answer = YES
12 Correct 0 ms 212 KB answer = NO
13 Correct 1 ms 212 KB answer = YES
14 Correct 1 ms 212 KB answer = YES
15 Correct 1 ms 212 KB answer = YES
16 Correct 1 ms 212 KB answer = YES
17 Correct 0 ms 212 KB answer = YES
18 Correct 0 ms 212 KB answer = YES
19 Correct 0 ms 212 KB answer = YES
20 Correct 0 ms 212 KB answer = YES
21 Correct 0 ms 212 KB answer = YES
22 Correct 0 ms 212 KB answer = NO
23 Correct 0 ms 212 KB answer = NO
24 Correct 1 ms 212 KB answer = YES
25 Correct 1 ms 212 KB answer = YES
26 Incorrect 1 ms 212 KB participant answer is larger than the answer of jury
27 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 0 ms 212 KB answer = YES
3 Correct 0 ms 212 KB answer = YES
4 Correct 0 ms 212 KB answer = NO
5 Correct 0 ms 212 KB answer = YES
6 Correct 1 ms 212 KB answer = YES
7 Correct 0 ms 212 KB answer = YES
8 Correct 0 ms 212 KB answer = YES
9 Correct 0 ms 212 KB answer = NO
10 Correct 0 ms 212 KB answer = YES
11 Correct 0 ms 212 KB answer = YES
12 Correct 0 ms 212 KB answer = NO
13 Correct 1 ms 212 KB answer = YES
14 Correct 1 ms 212 KB answer = YES
15 Correct 1 ms 212 KB answer = YES
16 Correct 1 ms 212 KB answer = YES
17 Correct 0 ms 212 KB answer = YES
18 Correct 0 ms 212 KB answer = YES
19 Correct 0 ms 212 KB answer = YES
20 Correct 0 ms 212 KB answer = YES
21 Correct 0 ms 212 KB answer = YES
22 Correct 0 ms 212 KB answer = NO
23 Correct 0 ms 212 KB answer = NO
24 Correct 1 ms 212 KB answer = YES
25 Correct 1 ms 212 KB answer = YES
26 Incorrect 1 ms 212 KB participant answer is larger than the answer of jury
27 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 0 ms 212 KB answer = YES
3 Correct 0 ms 212 KB answer = YES
4 Correct 0 ms 212 KB answer = NO
5 Correct 0 ms 212 KB answer = YES
6 Correct 1 ms 212 KB answer = YES
7 Correct 0 ms 212 KB answer = YES
8 Correct 0 ms 212 KB answer = YES
9 Correct 0 ms 212 KB answer = NO
10 Correct 0 ms 212 KB answer = YES
11 Correct 0 ms 212 KB answer = YES
12 Correct 0 ms 212 KB answer = NO
13 Correct 1 ms 212 KB answer = YES
14 Correct 1 ms 212 KB answer = YES
15 Correct 1 ms 212 KB answer = YES
16 Correct 1 ms 212 KB answer = YES
17 Correct 0 ms 212 KB answer = YES
18 Correct 0 ms 212 KB answer = YES
19 Correct 0 ms 212 KB answer = YES
20 Correct 0 ms 212 KB answer = YES
21 Correct 0 ms 212 KB answer = YES
22 Correct 0 ms 212 KB answer = NO
23 Correct 0 ms 212 KB answer = NO
24 Correct 1 ms 212 KB answer = YES
25 Correct 1 ms 212 KB answer = YES
26 Incorrect 1 ms 212 KB participant answer is larger than the answer of jury
27 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 0 ms 212 KB answer = YES
3 Correct 0 ms 212 KB answer = YES
4 Correct 0 ms 212 KB answer = NO
5 Correct 0 ms 212 KB answer = YES
6 Correct 1 ms 212 KB answer = YES
7 Correct 0 ms 212 KB answer = YES
8 Correct 0 ms 212 KB answer = YES
9 Correct 0 ms 212 KB answer = NO
10 Correct 0 ms 212 KB answer = YES
11 Correct 0 ms 212 KB answer = YES
12 Correct 0 ms 212 KB answer = NO
13 Correct 1 ms 212 KB answer = YES
14 Correct 1 ms 212 KB answer = YES
15 Correct 1 ms 212 KB answer = YES
16 Correct 1 ms 212 KB answer = YES
17 Correct 0 ms 212 KB answer = YES
18 Correct 0 ms 212 KB answer = YES
19 Correct 0 ms 212 KB answer = YES
20 Correct 0 ms 212 KB answer = YES
21 Correct 0 ms 212 KB answer = YES
22 Correct 0 ms 212 KB answer = NO
23 Correct 0 ms 212 KB answer = NO
24 Correct 1 ms 212 KB answer = YES
25 Correct 1 ms 212 KB answer = YES
26 Incorrect 1 ms 212 KB participant answer is larger than the answer of jury
27 Halted 0 ms 0 KB -