#include "bits/stdc++.h"
using namespace std;
#define int long long
signed main () {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
vector <pair <int, double>> g[n];
vector <double> node(n, (double)1e9), ans(n);
double mn = 1e9;
vector <int> v;
function<void(int)> dfs=[&](int v) {
node[v] = 0;
for(auto [i, j] : g[v]) {
if(!node[i]) continue;
dfs(i);
}
};
function <int(int,double)> check=[&](int v, double color) {
node[v] = color;
// cout << v << " " << color << "\n";
int f = 1;
for(auto [i,j] : g[v]) {
if(node[i] == 1e9) f = min(f, check(i, j-color));
else {
if(node[v] + node[i] != j) f = 0;
}
}
return f;
};
function<void(int, int)> rec=[&](int i, int sum) {
if(i == v.size()) {
if(mn > sum) {
mn = sum;
ans = node;
}
return;
}
for(double val = -2; val <= 2; val += 0.25) {
for(auto &j : node) j = 1e9;
if(check(v[i], val)) {
// cout << val << " " << i << "\n";
node[v[i]] = val;
rec(i + 1, sum + fabs(val));
node[v[i]] = 1e9;
}
// cout << "\n";
}
};
for(int i = 0; i < m; i ++) {
int u, v;
cin >> u >> v;
u --, v --;
int w;
cin >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
for(int i = 0; i < n; i ++) {
if(node[i] == 1e9) {dfs(i);v.push_back(i);}
}
// for(auto i : v) cout << i << " ";
for(auto &j : node) j = 1e9;
rec(0, 0);
if(mn == 1e9) cout << "NO";
else {
cout << "YES\n";
for(auto i : ans) cout << fixed << setprecision(6) << i << " ";
}
return 0;
}
Compilation message
Village.cpp: In lambda function:
Village.cpp:18:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
18 | for(auto [i, j] : g[v]) {
| ^
Village.cpp: In lambda function:
Village.cpp:27:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
27 | for(auto [i,j] : g[v]) {
| ^
Village.cpp: In lambda function:
Village.cpp:36:8: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | if(i == v.size()) {
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Expected integer, but "YES" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Expected integer, but "NO" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Expected integer, but "YES" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
