Submission #932125

#	Time	Username	Problem	Language	Result	Execution time	Memory
932125		Jawad_Akbar_JJ	Graph (BOI20_graph)	C++17	0 / 100	4 ms	11444 KiB

Graph

#include <iostream>
#include <vector>
#include <iomanip>

using namespace std;
#define ld long double
const int N = 2e5 + 10;
vector<pair<int,int>> nei[N];
int l[N],r[N],c[N];
ld a[N],b[N],inf = 1e9;
int pen[100];

void dfs1(int u,int p = 0,int v = 0,int last = 0){
	if (v >= 10){
		last += pen[v];
		if (a[u] != inf){
			if (a[u] != last){
				cout<<"NO\n";
				exit(0);
			}
			return;
		}
		a[u] = last;
		v = 0;
	}
	v *= 10;
	for (auto [i,j] : nei[u]){
		if (i == p)
			continue;
		dfs1(i,u,v + j,last);
	}
}
void dfs2(int u,int p = 0,int v = 0,int last = 0){
	if (v >= 10){
		last += pen[v];
		if (b[u] != inf){
			if (b[u] != last){
				cout<<"NO\n";
				exit(0);
			}
			return;
		}
		b[u] = last;
		v = 0;
	}
	v *= 10;
	for (auto [i,j] : nei[u]){
		if (i == p)
			continue;
		dfs2(i,u,v * 10 + j,last);
	}
}
ld k;
ld calc(ld v,int n){
	ld ans = 0;
	for (int i=1;i<=n;i++){
		if (a[i] != inf)
			ans += abs(v + a[i]);
		else
			ans += abs(k - v + b[i]);
	}
	return ans;
}

signed  main(){
	cout<<fixed<<setprecision(9);
	int n,m;
	cin>>n>>m;
	pen[21] = -1;
	pen[12] = +1;

	for (int i=1;i<=n;i++)
		a[i] = b[i] = inf;

	for (int i=1;i<=m;i++){
		int u,v,t;
		cin>>u>>v>>t;
		l[i] = u;
		r[i] = v;
		c[i] = t;
		nei[u].push_back({v,t});
		nei[v].push_back({u,t});
	}
	a[1] = 0;
	dfs1(1);

	for (int i=1;i<=m;i++){
		if (a[l[i]] != inf and a[r[i]] != inf){
			ld A = (c[i] - a[l[i]] - a[r[i]]) / 2.0;
			cout<<"YES\n";
			for (int j=1;j<=n;j++)
				cout<<A + a[j]<<" ";
			cout<<endl;
			return 0;
		}
	}

	int r2 = nei[1][0].first;
	b[r2] = 0;

	dfs2(r2);

	k = nei[1][0].second;

	ld lft = -1e5,rgt = k / 2.0;

	while (rgt - lft > 0.00000001){
		ld mid = (lft + rgt)/2.0;
		ld frst = calc(mid,n);
		ld sec = calc(min(rgt,mid + 0.00000001),n);
		if (frst < sec)
			rgt = mid;
		else
			lft = mid;
		// cout<<lft<<" "<<rgt<<" "<<mid<<" "<<frst<<" "<<sec<<endl;
	}
	// cout<<calc(0,n)<<endl;
	cout<<"YES"<<endl;
	for (int i=1;i<=n;i++)
		if (a[i] != inf)
			cout<<lft + a[i]<<" ";
		else
			cout<<k - lft + b[i]<<" ";
	cout<<endl;

}

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