Submission #1184686

#TimeUsernameProblemLanguageResultExecution timeMemory
1184686kl0989eGraph (BOI20_graph)C++20
5 / 100
7 ms10568 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

const int maxn=2e5+10;

struct eq {
	int a=-1e9,b=-1e9;//a*x+b

	eq(int _a=-1e9, int _b=-1e9): a(_a),b(_b) {}

	long double sol(eq o) {
		if (a==o.a) {
			if (b==o.b) {
				return 1e9;
			}
			return -1e9;
		}
		return (1.0*o.b-b)/(a-o.a);
	}

	long double get(long double x) {
		return a*x+b;
	}
};

vector<vector<pi>> graph(maxn);
vector<long double> vals(maxn,1e9);
vi seen(maxn,0);
vector<eq> eqs(maxn);

long double sol=1e9;
vi comp;

void dfs(int cur) {
	seen[cur]=1;
	comp.pb(cur);
	for (auto [to,v]:graph[cur]) {
		eq temp={-eqs[cur].a,v-eqs[cur].b};
		if (seen[to]) {
			long double newsol=temp.sol(eqs[to]);
			if (newsol==1e9) {
				continue;
			}
			if (sol!=1e9 && abs(sol-newsol)>1e-9) {
				sol=-1e9;
				return;
			}
			else {
				sol=newsol;
			}
		}
		else {
			eqs[to]=temp;
			dfs(to);
		}
	}
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
	int n,m;
	cin >> n >> m;
	int a,b,c;
	for (int i=0; i<m; i++) {
		cin >> a >> b >> c;
		graph[--a].pb({--b,c});
		graph[b].pb({a,c});
	}
	for (int i=0; i<n; i++) {
		if (!seen[i]) {
			sol=1e9;
			comp.clear();
			eqs[i]={1,0};
			dfs(i);
			if (sol==-1e9) {
				cout << "NO\n";
				return 0;
			}
			else if (sol!=1e9) {
				for (auto a:comp) {
					vals[a]=eqs[a].get(sol);
				}
			}
			else {
				int sum=1e9;
				for (auto [l,r]:vector<pi>({{-1e9,-2},{-2,-1},{-1,0},{0,1},{1,2},{2,1e9}})) {
					int a=0, b=0;
					for (auto cur:comp) {
						if (eqs[cur].get(l)<=0 && eqs[cur].get(r)<=0) {
							a-=eqs[cur].a;
							b-=eqs[cur].b;
						}
						else {
							a+=eqs[cur].a;
							b+=eqs[cur].b;
						}
					}
					if (a!=0) {
						sol=-b/a;
					}
					else {
						sol=0;
					}
					sol=max((long double)l,min((long double)r,sol));
					if (a*sol+b<=sum) {
						sum=a*sol+b;
						for (auto cur:comp) {
							vals[cur]=eqs[cur].get(sol);
						}
					}
				}
			}
		}
	}
	cout << "YES\n" << fixed << setprecision(12);
	for (int i=0; i<n; i++) {
		cout << vals[i] << " \n"[i==n-1];
	}
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...