Submission #1184703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184703		kl0989e	Graph (BOI20_graph)	C++20	100 / 100	255 ms	29748 KiB

Graph

#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 {
	long double a=-1e15,b=-1e15;//a*x+b

	eq(long double _a=-1e15, long double _b=-1e15): a(_a),b(_b) {}

	long double sol(eq o) {
		if (a==o.a) {
			if (b==o.b) {
				return 1e15;
			}
			return -1e15;
		}
		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,1e15);
vi seen(maxn,0);
vector<eq> eqs(maxn);

long double sol=1e15;
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==1e15) {
				continue;
			}
			if (sol!=1e15 && abs(sol-newsol)>1e-9) {
				sol=-1e15;
				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=1e15;
			comp.clear();
			eqs[i]={1,0};
			dfs(i);
			if (sol==-1e15) {
				cout << "NO\n";
				return 0;
			}
			else if (sol!=1e15) {
				for (auto a:comp) {
					vals[a]=eqs[a].get(sol);
				}
			}
			else {
				long double sum=1e15;
				for (auto [l,r]:vector<pair<long double,long double>>({{-100,-2},{-2,-1},{-1,0},{0,1},{1,2},{2,100}})) {
					while (abs(r-l)>=1e-12) {
						long double m1=l+(r-l)/2;
						long double m2=m1-(r-l)/8;
						long double s1=0,s2=0;
						for (auto cur:comp) {
							s1+=abs(eqs[cur].get(m1));
							s2+=abs(eqs[cur].get(m2));
						}
						if (s2<=s1) {
							r=m1;
						}
						else {
							l=m2;
						}
					}
					long double m=l+(r-l)/2;
					long double s=0;
					for (auto cur:comp) {
						s+=abs(eqs[cur].get(m));
					}
					if (s<=sum) {
						sum=s;
						for (auto cur:comp) {
							vals[cur]=eqs[cur].get(m);
						}
					}
				}
			}
		}
	}
	cout << "YES\n" << fixed << setprecision(12);
	for (int i=0; i<n; i++) {
		cout << vals[i] << " \n"[i==n-1];
	}
    return 0;
}

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