Submission #467332

#	Time	Username	Problem	Language	Result	Execution time	Memory
467332		MVP_Harry	Graph (BOI20_graph)	C++17	100 / 100	193 ms	19944 KiB

Graph

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define rep(i, m, n) for (int i = m; i <= n; i++)
#define per(i, m, n) for (int i = m; i >= n; i--)
#define sz(v) (int) v.size()
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second

const int maxn = 1e5 + 5;
const double eps = 1e-6;

int N, M, leader, impossible, cycle = 0;
int vis[maxn];
double a[maxn];
vector<pair<int, int> > G[maxn];
vector<int> pt;
pair<int, int> c[maxn];

void dfs1(int u, int par) {
	vis[u] = 2;
	for (auto node : G[u]) {
		int v = node.fi, x = node.se;
		if (v == par) continue;
		if (vis[v] == 2) {
			// consider c[u], c[v]
			if (c[u].se + c[v].se == 0) {
				if (c[u].fi + c[v].fi != x) impossible = 1;
				else continue;
			}
			cycle = 1;
			double val = (double) (x - c[u].fi - c[v].fi) / (c[u].se + c[v].se);
			if (a[leader] == INF) a[leader] = val;
			else {
				if (abs(a[leader] - val) > eps) impossible = 1;
			}
		} else {
			c[v] = mp(x - c[u].fi, -c[u].se);
			dfs1(v, u);
		}
	}
}

void dfs2(int u, int par) {
	vis[u] = 3;
	pt.push_back((-c[u].se) * c[u].fi);
	for (auto node : G[u]) {
		if (node.fi == par || vis[node.fi] == 3) continue;
		dfs2(node.fi, u);
	}
}

void dfs3(int u, int par) {
	vis[u] = 1;
	if (u != leader) a[u] = (double) c[u].fi + (double) c[u].se * a[leader];
	for (auto node : G[u]) {
		if (node.fi == par || vis[node.fi] == 1) continue;
		dfs3(node.fi, u);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N >> M;
	rep(i, 1, M) {
		int u, v, x;
		cin >> u >> v >> x;
		G[u].push_back(mp(v, x)), G[v].push_back(mp(u, x));
	}
	rep(i, 1, N) a[i] = INF;
	rep(i, 1, N) if (!vis[i]) {
		c[i] = mp(0, 1);
		leader = i, cycle = 0;
		dfs1(i, 0);
		if (impossible) {
			cout << "NO\n";
			return 0;
		}
		if (!cycle) {
			pt.clear();
			dfs2(i, 0);
			sort(all(pt));
			a[leader] = pt[(sz(pt) - 1) / 2];
		}
		dfs3(i, 0);
	}
	cout << "YES\n";
	rep(i, 1, N) cout << a[i] << " ";
	cout << "\n";
	return 0;
}

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