/**
* author: kututay
* created: 20.09.2022 13:13:02
**/
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/Users/kutay/CP/templates/debug.h"
#else
#define debug(...) void(38)
#endif
const double epsilon = 1e-6;
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, m; cin >> n >> m;
vector<vector<pair<int, int>>> g(n);
vector<pair<pair<int, int>, int>> edges;
for (int i = 0; i < m; i++) {
int x, y, z; cin >> x >> y >> z, x--, y--;
g[x].emplace_back(y, z);
g[y].emplace_back(x, z);
edges.emplace_back(make_pair(x, y), z);
}
vector<double> ans(n);
vector<int> components_vis(n);
vector<pair<int, int>> n_vals(n); // (first * x + second) - node values
auto solve = [&](int node) {
vector<int> cycle_vis(n);
bool cycle = false;
vector<int> nodes;
double x;
bool flag = false;
function<void(int, int, int)> find_cycle = [&](int node, int parent, int color) {
cycle_vis[node] = 1;
components_vis[node] = 1;
nodes.emplace_back(node);
for (auto next : g[node]) {
if (parent == -1) n_vals[node] = make_pair(1, 0);
else n_vals[node] = make_pair(-n_vals[parent].first, color - n_vals[parent].second);
auto p = make_pair(node, next.first);
auto col = next.second;
auto a = n_vals[p.first];
auto b = n_vals[p.second];
pair<int, int> should = make_pair(-a.first, col - a.second);
if (b == should) continue;
pair<int, int> sum = make_pair(b.first + a.first, col - (b.second + a.second));
if (sum.first == 0) {
cout << "NO\n";
exit(0);
}
if (flag == false) x = (double) sum.second / sum.first;
flag = true;
if (cycle_vis[next.first]) {
cycle = true;
continue;
}
if (next.first != parent) find_cycle(next.first, node, next.second);
}
ans[node] = n_vals[node].first * x + n_vals[node].second;
};
find_cycle(node, -1, -1);
if ((int) nodes.size() == 0) return;
if (flag == false or cycle == false) {
int N = 101;
vector<double> s(2 * N + 1);
for (int i : nodes) {
for (int j = -N; j < N; j++) {
s[j + N] += abs(n_vals[i].first * j + n_vals[i].second);
}
}
int mn = 1e9;
for (int j = -N; j < N; j++) {
if (s[j + N] < mn) {
x = j;
mn = s[j + N];
}
}
debug(x);
for (int i : nodes) {
ans[i] = n_vals[i].first * x + n_vals[i].second;
}
return;
}
};
for (int i = 0; i < n; i++) {
if (components_vis[i]) continue;
solve(i);
}
for (auto [p, color] : edges) {
double sum = ans[p.first] + ans[p.second];
if (abs(sum - color) > epsilon) {
cout << "NO\n";
exit(0);
}
}
cout << "YES\n";
for (auto x : ans) cout << fixed << setprecision(6) << x << " ";
cout << '\n';
double top = 0;
for (auto x : ans) top += abs(x);
debug(ans.size(), top);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
jury has the better answer: jans = YES, pans = NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
jury has the better answer: jans = YES, pans = NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
jury has the better answer: jans = YES, pans = NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
jury has the better answer: jans = YES, pans = NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
jury has the better answer: jans = YES, pans = NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
