oj.uz

Submission #654886

# Submission time Handle Problem Language Result Execution time Memory
654886 2022-11-01T20:38:09 Z inksamurai Graph (BOI20_graph) C++17
58 / 100
 700 ms 25224 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#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);
	vec(ld) rbts;
	auto affine_=[&](int rt,ld x,int t=0)->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;
			}
			if(t) rbts.pb(rbe[v]);
			res+=abs(rbe[v]);
			usd2[v]=0;
		}
		return res;
	};

	auto slv=[&](int rt)->void{
		ld l=-1e9,r=1e9;
		rep(_,150){
			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 1 ms 256 KB answer = YES
3 Correct 1 ms 212 KB answer = YES
4 Correct 0 ms 212 KB answer = NO
5 Correct 1 ms 212 KB answer = YES
6 Correct 1 ms 212 KB answer = YES
7 Correct 0 ms 212 KB answer = YES
8 Correct 1 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 276 KB answer = YES
12 Correct 0 ms 212 KB answer = NO
13 Correct 0 ms 212 KB answer = YES
14 Correct 1 ms 212 KB answer = YES
15 Correct 0 ms 212 KB answer = YES
16 Correct 1 ms 212 KB answer = YES
17 Correct 1 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
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB answer = YES
2 Correct 1 ms 256 KB answer = YES
3 Correct 1 ms 212 KB answer = YES
4 Correct 0 ms 212 KB answer = NO
5 Correct 1 ms 212 KB answer = YES
6 Correct 1 ms 212 KB answer = YES
7 Correct 0 ms 212 KB answer = YES
8 Correct 1 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 276 KB answer = YES
12 Correct 0 ms 212 KB answer = NO
13 Correct 0 ms 212 KB answer = YES
14 Correct 1 ms 212 KB answer = YES
15 Correct 0 ms 212 KB answer = YES
16 Correct 1 ms 212 KB answer = YES
17 Correct 1 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 2 ms 212 KB answer = YES
25 Correct 1 ms 212 KB answer = YES
26 Correct 1 ms 212 KB answer = YES
27 Correct 1 ms 212 KB answer = YES
28 Correct 1 ms 340 KB answer = YES
29 Correct 1 ms 212 KB answer = YES
30 Correct 1 ms 212 KB answer = NO
31 Correct 1 ms 212 KB answer = YES
32 Correct 1 ms 212 KB answer = YES
33 Correct 2 ms 212 KB answer = YES
34 Correct 1 ms 340 KB answer = YES
35 Correct 1 ms 212 KB answer = YES
36 Correct 1 ms 212 KB answer = YES

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB answer = YES
2 Correct 1 ms 256 KB answer = YES
3 Correct 1 ms 212 KB answer = YES
4 Correct 0 ms 212 KB answer = NO
5 Correct 1 ms 212 KB answer = YES
6 Correct 1 ms 212 KB answer = YES
7 Correct 0 ms 212 KB answer = YES
8 Correct 1 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 276 KB answer = YES
12 Correct 0 ms 212 KB answer = NO
13 Correct 0 ms 212 KB answer = YES
14 Correct 1 ms 212 KB answer = YES
15 Correct 0 ms 212 KB answer = YES
16 Correct 1 ms 212 KB answer = YES
17 Correct 1 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 2 ms 212 KB answer = YES
25 Correct 1 ms 212 KB answer = YES
26 Correct 1 ms 212 KB answer = YES
27 Correct 1 ms 212 KB answer = YES
28 Correct 1 ms 340 KB answer = YES
29 Correct 1 ms 212 KB answer = YES
30 Correct 1 ms 212 KB answer = NO
31 Correct 1 ms 212 KB answer = YES
32 Correct 1 ms 212 KB answer = YES
33 Correct 2 ms 212 KB answer = YES
34 Correct 1 ms 340 KB answer = YES
35 Correct 1 ms 212 KB answer = YES
36 Correct 1 ms 212 KB answer = YES
37 Correct 2 ms 340 KB answer = YES
38 Correct 1 ms 340 KB answer = YES
39 Correct 6 ms 440 KB answer = YES
40 Correct 1 ms 468 KB answer = YES
41 Correct 1 ms 468 KB answer = NO
42 Correct 12 ms 468 KB answer = YES
43 Correct 12 ms 468 KB answer = YES
44 Correct 13 ms 524 KB answer = YES
45 Correct 2 ms 468 KB answer = YES
46 Correct 6 ms 340 KB answer = YES
47 Correct 1 ms 468 KB answer = YES
48 Correct 2 ms 468 KB answer = YES

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB answer = YES
2 Correct 1 ms 256 KB answer = YES
3 Correct 1 ms 212 KB answer = YES
4 Correct 0 ms 212 KB answer = NO
5 Correct 1 ms 212 KB answer = YES
6 Correct 1 ms 212 KB answer = YES
7 Correct 0 ms 212 KB answer = YES
8 Correct 1 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 276 KB answer = YES
12 Correct 0 ms 212 KB answer = NO
13 Correct 0 ms 212 KB answer = YES
14 Correct 1 ms 212 KB answer = YES
15 Correct 0 ms 212 KB answer = YES
16 Correct 1 ms 212 KB answer = YES
17 Correct 1 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 2 ms 212 KB answer = YES
25 Correct 1 ms 212 KB answer = YES
26 Correct 1 ms 212 KB answer = YES
27 Correct 1 ms 212 KB answer = YES
28 Correct 1 ms 340 KB answer = YES
29 Correct 1 ms 212 KB answer = YES
30 Correct 1 ms 212 KB answer = NO
31 Correct 1 ms 212 KB answer = YES
32 Correct 1 ms 212 KB answer = YES
33 Correct 2 ms 212 KB answer = YES
34 Correct 1 ms 340 KB answer = YES
35 Correct 1 ms 212 KB answer = YES
36 Correct 1 ms 212 KB answer = YES
37 Correct 2 ms 340 KB answer = YES
38 Correct 1 ms 340 KB answer = YES
39 Correct 6 ms 440 KB answer = YES
40 Correct 1 ms 468 KB answer = YES
41 Correct 1 ms 468 KB answer = NO
42 Correct 12 ms 468 KB answer = YES
43 Correct 12 ms 468 KB answer = YES
44 Correct 13 ms 524 KB answer = YES
45 Correct 2 ms 468 KB answer = YES
46 Correct 6 ms 340 KB answer = YES
47 Correct 1 ms 468 KB answer = YES
48 Correct 2 ms 468 KB answer = YES
49 Correct 204 ms 2628 KB answer = YES
50 Correct 13 ms 2728 KB answer = YES
51 Correct 161 ms 2784 KB answer = YES
52 Correct 8 ms 2644 KB answer = NO
53 Correct 14 ms 468 KB answer = YES
54 Correct 31 ms 844 KB answer = YES
55 Correct 88 ms 1396 KB answer = YES
56 Correct 202 ms 2492 KB answer = YES
57 Correct 152 ms 2460 KB answer = YES
58 Correct 144 ms 2228 KB answer = YES
59 Correct 12 ms 2260 KB answer = YES
60 Correct 186 ms 2568 KB answer = YES
61 Correct 7 ms 1492 KB answer = YES
62 Correct 182 ms 17568 KB answer = NO
63 Correct 210 ms 18640 KB answer = YES
64 Correct 182 ms 18480 KB answer = NO
65 Correct 216 ms 18616 KB answer = YES
66 Correct 24 ms 740 KB answer = YES

Subtask #5
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB answer = YES
2 Correct 1 ms 256 KB answer = YES
3 Correct 1 ms 212 KB answer = YES
4 Correct 0 ms 212 KB answer = NO
5 Correct 1 ms 212 KB answer = YES
6 Correct 1 ms 212 KB answer = YES
7 Correct 0 ms 212 KB answer = YES
8 Correct 1 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 276 KB answer = YES
12 Correct 0 ms 212 KB answer = NO
13 Correct 0 ms 212 KB answer = YES
14 Correct 1 ms 212 KB answer = YES
15 Correct 0 ms 212 KB answer = YES
16 Correct 1 ms 212 KB answer = YES
17 Correct 1 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 2 ms 212 KB answer = YES
25 Correct 1 ms 212 KB answer = YES
26 Correct 1 ms 212 KB answer = YES
27 Correct 1 ms 212 KB answer = YES
28 Correct 1 ms 340 KB answer = YES
29 Correct 1 ms 212 KB answer = YES
30 Correct 1 ms 212 KB answer = NO
31 Correct 1 ms 212 KB answer = YES
32 Correct 1 ms 212 KB answer = YES
33 Correct 2 ms 212 KB answer = YES
34 Correct 1 ms 340 KB answer = YES
35 Correct 1 ms 212 KB answer = YES
36 Correct 1 ms 212 KB answer = YES
37 Correct 2 ms 340 KB answer = YES
38 Correct 1 ms 340 KB answer = YES
39 Correct 6 ms 440 KB answer = YES
40 Correct 1 ms 468 KB answer = YES
41 Correct 1 ms 468 KB answer = NO
42 Correct 12 ms 468 KB answer = YES
43 Correct 12 ms 468 KB answer = YES
44 Correct 13 ms 524 KB answer = YES
45 Correct 2 ms 468 KB answer = YES
46 Correct 6 ms 340 KB answer = YES
47 Correct 1 ms 468 KB answer = YES
48 Correct 2 ms 468 KB answer = YES
49 Correct 204 ms 2628 KB answer = YES
50 Correct 13 ms 2728 KB answer = YES
51 Correct 161 ms 2784 KB answer = YES
52 Correct 8 ms 2644 KB answer = NO
53 Correct 14 ms 468 KB answer = YES
54 Correct 31 ms 844 KB answer = YES
55 Correct 88 ms 1396 KB answer = YES
56 Correct 202 ms 2492 KB answer = YES
57 Correct 152 ms 2460 KB answer = YES
58 Correct 144 ms 2228 KB answer = YES
59 Correct 12 ms 2260 KB answer = YES
60 Correct 186 ms 2568 KB answer = YES
61 Correct 7 ms 1492 KB answer = YES
62 Correct 182 ms 17568 KB answer = NO
63 Correct 210 ms 18640 KB answer = YES
64 Correct 182 ms 18480 KB answer = NO
65 Correct 216 ms 18616 KB answer = YES
66 Correct 24 ms 740 KB answer = YES
67 Execution timed out 1100 ms 25224 KB Time limit exceeded
68 Halted 0 ms 0 KB -