Submission #1055556

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055556		Nonoze	Graph (BOI20_graph)	C++17	100 / 100	296 ms	49424 KiB

Graph

/*
*	Author: Nonoze
*	Created: Wednesday 07/08/2024
*/
#include <bits/stdc++.h>
using namespace std;


#ifndef _IN_LOCAL
	#define dbg(...)
#endif

#define endl '\n'
#define endlfl '\n' << flush
#define quit(x) return (void)(cout << x << endl)

#define sz(x) (int)(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define cmin(a, b) a = min(a, b)
#define cmax(a, b) a = max(a, b)

#define int long long
const int inf = numeric_limits<int>::max() / 4;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1e9+7, LOG=25;



void solve();

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;
	// cin >> tt;
	while(tt--) solve();
	return 0;
}




int n, k, m, q;
vector<pair<int, int>> adj[100000];
vector<bool> visited(100000);
int weights[100000], obligated[100000];

vector<vector<int>> contains;
vector<int> roots;

void dfspre(int u) {
	visited[u]=1;
	contains.back().pb(u);
	for (auto [v, w] : adj[u]) if (!visited[v]) dfspre(v);
}

void precalc() {
	for (int i=0; i<n; i++) if (!visited[i]) {
		contains.pb({});
		dfspre(i);
		roots.pb(i);
	}
}

int toadd=-inf;
vector<int> colors(100000);

int dfs(int u, bool color=0) {
	if (obligated[u]!=-inf && weights[u]!=obligated[u]) return inf;
	colors[u]=color;
	int act=abs(weights[u]);
	for (auto [v, w]: adj[u]) {
		if (weights[v]!=-inf) {
			if (weights[v]+weights[u]==w || colors[v]!=colors[u]) continue;
			toadd=w-(weights[u]+weights[v]);
			if (color) toadd*=-1;
			toadd/=2;
			continue;
		}
		if (weights[v]!=-inf) {
			if (weights[v]+weights[u]!=w) return inf;
			continue;
		}
		weights[v]=w-weights[u];
		int t=dfs(v, color^1);
		if (t==inf) return inf;
		act+=t;
	}
	return act;
}

int calcw(int src, int empl, int w) {
	toadd=inf;
	for (auto u: contains[empl]) weights[u]=-inf;
	weights[src]=w;
	return dfs(src);
}

int calc(int src, int empl) {
	int l=-1000, r=1000, ans=0;
	while (l<=r) {
		int mid=(l+r)/2;
		int t1=calcw(src, empl, mid-1), t2=calcw(src, empl, mid+1), t=calcw(src, empl, mid);
		if (t<t1 && t<t2) return t;
		if (t1<t2) r=mid-1, ans=mid-1;
		else l=mid+1, ans=mid+1;
	}
	calcw(src, empl, ans);
	return ans;
}

void solve() {
	cin >> n >> m;
	map<int, int> ver[n];
	for (int i=0; i<n; i++) weights[i]=obligated[i]=-inf;
	for (int i=0; i<m; i++) {
		int u, v, w; cin >> u >> v >> w; u--, v--; if (v<u) swap(u, v);
		if (u==v) {
			if (obligated[u]!=-inf && obligated[u]!=w) quit("NO");
			obligated[u]=w;
			continue;
		}
		if (ver[u].count(v)) {
			if (ver[u][v]==w*2) continue;
			else quit("NO");
		}
		ver[u][v]=w*2;
		adj[u].pb({v, w*2});
		adj[v].pb({u, w*2});
	}
	precalc();
	int empl=-1;
	for (auto src: roots) {
		empl++;
		int obl=-1;
		for (auto u: contains[empl]) if (obligated[u]!=-inf) obl=u;
		if (obl!=-1) {
			src=obl;
			calcw(src, empl, obligated[src]);
			if (toadd!=inf) quit("NO");
			continue;
		}
		calcw(src, empl, 0);
		if (toadd==inf) {
			calcw(src, empl, 1);
			if (toadd==inf) calc(src, empl);
			else calcw(src, empl, 0);
			continue;
		}
		calcw(src, empl, toadd);
		if (toadd!=inf) quit("NO");
	}
	for (int u=0; u<n; u++) {
		for (auto [v, w]: adj[u]) {
			if (weights[v]+weights[u]!=w) quit("NO");
		}
	}
	cout << "YES" << endl;
	for (int i=0; i<n; i++) cout << (double)weights[i]/2 << ' ';
}

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