Submission #932269

#	Time	Username	Problem	Language	Result	Execution time	Memory
932269		Jawad_Akbar_JJ	Graph (BOI20_graph)	C++14	0 / 100	4 ms	15196 KiB

Graph

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

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

map<pair<int,int>,int> mp;
int T = 1;
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 : nei[u]){
		if (i[0] == p)
			continue;
		dfs1(i[0],u,v + i[1],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 : nei[u]){
		if (i[0] == p)
			continue;
		dfs2(i[0],u,v + i[1],last);
	}
}
ld k;

void dfs3(int u){
	for (auto i : nei[u]){
		if (ans[i[0]] != inf)
			continue;
		ans[i[0]] = i[1] - ans[u];
		dfs3(i[0]);
	}
}
vector<int> vec,vv;

void get(int u){
	seen[u] = true;
	vv.push_back(u);
	for (auto v : nei[u]){
		if (seen[v[0]])
			continue;
		vec.push_back({v[2]});
		get(v[0]);
	}
}

ld calc(ld v){
	ld ans = 0;
	for (int i : vv){
		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] = ans[i] = inf;
	int cur = 1;
	for (int i=1;i<=m;i++){
		int u,v,t;
		cin>>u>>v>>t;
		if (mp[{u,v}] != 0){
			if (mp[{u,v}] == t)
				continue;
			cout<<"NO"<<endl;
			exit(0);
		}
		l[cur] = u;
		r[cur] = v;
		c[cur] = t;
		cur++;
		nei[u].push_back({v,t,i});
		nei[v].push_back({u,t,i});
		mp[{u,v}] = mp[{v,u}] = t;
	}
	m = cur - 1;



	for (int i=1;i<=n;i++){
		if (seen[i] or nei[i].size() == 0)
			continue;
		vec.clear();
		vv.clear();
		get(i);
		bool con = false;
		for (int j : vec)
			if (l[j] == r[j]){
				ans[l[j]] = c[j] / 2.0;
				dfs3(l[j]);
				con = true;
				break;
			}
		if (con)
			continue;
		a[i] = 0;
		dfs1(i);
		int u = nei[i][0][0];
		if (a[u] != inf){
			ld A = nei[i][0][1] - a[u];
			A = A / 2.0;
			ans[i] = A;
			dfs3(i);
			continue;
		}
		dfs2(u);
		k = nei[i][0][1];

		ld lft = -1e5,rgt = nei[i][0][1];

		while (rgt - lft > 0.00000000001){
			ld mid = (lft + rgt)/2.0;
			ld frst = calc(mid);
			ld sec = calc(mid + 0.00000000001);
			if (frst < sec)
				rgt = mid;
			else
				lft = mid;
		}
		ans[i] = lft;
		dfs3(i);
	}

	for (int i=1;i<=n;i++)
		if (ans[i] == inf)
			ans[i] = 0;

	for (int i=1;i<=m;i++){
		if (abs(c[i] - ans[l[i]] - ans[r[i]]) > 0.000001){
			cout<<"NO"<<endl;
			return 0;
		}
	}

	cout<<"YES"<<endl;
	for (int i=1;i<=n;i++)
		cout<<ans[i]<<" ";
	cout<<endl;
	
	

}

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