Submission #751587

#	Time	Username	Problem	Language	Result	Execution time	Memory
751587		javotaz	Graph (BOI20_graph)	C++17	100 / 100	194 ms	20972 KiB

Graph

// be nam khodavand jano kherad     kazin bartar andishe bar nagzarad
#include<bits/stdc++.h>
using namespace std;
 
const int N = 1e5 + 12;
int n, m, bakhsh[N], omgh[N];
double x[N], check;
bool mrk[N];
vector<pair<int, int> > g[N], xs;
 
void output() {
	cout << "YES\n";
	for (int i = 1; i <= n; i++)
		cout << x[i] << ' ';
}
 
void wrong_output() {
	cout << "NO\n";
	exit(0);
}
 
void check_ans(int a) {
	for (auto i: g[a]) {
		int v = i.first;
		int dis = i.second;
		if (mrk[v]) {
			if (dis - x[a] != x[v])
				wrong_output();
		}
		else {
			mrk[v] = true;
			x[v] = dis - x[a];
			check_ans(v);
		}
	}
}
 
void dfs(int u) {
	for (auto i: g[u]) {
		int v = i.first;
		if (omgh[v] == omgh[u]) {
			check = (x[v] * -1 * omgh[v] + ((i.second - x[u]) * omgh[u])) / 2.0; 
			return;
		}
		if (!omgh[v]) {
			omgh[v] = omgh[u] * -1;
			x[v] = i.second - x[u];  
			dfs(v);
		}
	}
}
 
void dfs_fill_x(int a) {
	for (auto i: g[a]) {
		int u = i.first;
		omgh[u] = omgh[a] * -1;
		int tmp = (i.second - omgh[a] * x[a]) * omgh[u];
		if (mrk[u]) {
			if (x[u] != tmp)
				wrong_output();
		}
		else {
			x[u] = tmp;
			xs.push_back({tmp, u});
			mrk[u] = true;
			dfs_fill_x(u);
		}
	}
}
 
void minimize_output() {
	sort(xs.begin(), xs.end());
	int tmp = xs.size();
	tmp /= 2;
	int r = xs[tmp].first;
	for (auto i: xs) 
		x[i.second] = (i.first - r) * omgh[i.second];
}
 
bool do_bakhshi(int u) {
	bool res = true;
	for (auto i: g[u]) {
		int v = i.first;
		if (bakhsh[v] == bakhsh[u])
			return false;
		if (!bakhsh[v]) {
			bakhsh[v] = (bakhsh[u] == 1)? 2 : 1;
			res &= do_bakhshi(v);
		}
	}
	return res;
}
 
void solve() {
	for (int i = 1; i <= n; i++) {
		if (!mrk[i]) {
			xs.clear();
			xs.push_back({0, i});
			check = 0;
			bakhsh[i] = 1;
			omgh[i] = 1;
			mrk[i] = true;
			if (do_bakhshi(i)) dfs_fill_x(i), minimize_output();
			else {
				dfs(i);
				x[i] = check;
				check_ans(i);
			}
		}
	}
}
 
void input() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v, color;
		cin >> u >> v >> color;
		g[u].push_back({v, color});
		g[v].push_back({u, color});
	}
}
 
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	input(), solve(), output();
}
 
// migan garme bazar kheila

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