#include<bits/stdc++.h>
#define int long long
#define pii pair<long long, long long>
#define INF 1000000000000000000
using namespace std;
int n, m;
vector<vector<pii> >G;
vector<pii>v;
double k = 0;
int can = -1; // -1 unknown 0 wrong 1 can
int N = 20005;
struct Seg{
int n;
vector<int>arr;
Seg (int _n) {
n = _n;
arr = vector<int>(_n*4, 0);
}
void clear() {
for (int i = 0 ; i < n*4 ; i++) {
arr[i] = 0;
}
}
void add(int l, int r, int a, int c) { //c == 0 left c == 1 right
l += N, r += N;
if (c == 0) {
for (int i = r ; i >= l ; i--) {
arr[i] += a;
a++;
}
} else {
for (int i = l ; i <= r ; i++) {
arr[i] += a;
a++;
}
}
}
int query(int l, int r) {
l += N, r += N;
int ans = INF, pos;
for (int i = l ; i <= r ; i++) {
if (arr[i] < ans){
ans = arr[i];
pos = i;
}
}
return pos;
}
/*void add(int l, int r, int ql, int qr, int a, int i) {
if (ql <= l && r <= qr) {
arr[i] +=
}
}*/
};
vector<pair<int, pii> >nums;
vector<double>ans;
void dfs(int x, int p) {
nums.push_back({x, v[x]});
if (can == 0) return;
auto [f, s] = v[x];
for (auto [i, c] : G[x]) {
if (i == p) continue;
if (i == x) {
double newk = (double)(c - s - s) / (f + f);
if (can == 1) {
if (k != newk) can = 0;
} else {
k = newk; can = 1;
}
}
else if (v[i].first != 0) {
auto [f2, s2] = v[i];
if (f == -f2) {
if (s + s2 != c) can = 0;
} else {
double newk = (double)(c - s - s2) / (f + f2);
if (can == 1) {
if (k != newk) can = 0;
} else {
k = newk; can = 1;
}
}
continue;
}
if (c == 1) v[i] = {-f, 1-s};
else v[i] = {-f, 2-s};
dfs(i, x);
if (can == 0) return;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
G.resize(n);
v = vector<pii>(n, {0ll, 0ll});
ans.resize(n);
for (int i = 0 ; i < m ; i++) {
int a, b, c;
cin >> a >> b >> c; a--, b--;
G[a].push_back({b, c});
G[b].push_back({a, c});
}
Seg seg(N*2);
for (int i = 0 ; i < n ; i++) {
if (v[i].first == 0) {
v[i] = {1, 0};
can = -1;
dfs(i, -1);
if (can == 0) {
cout << "NO\n";
return 0;
}
if (can == -1) {
for (auto [x, vx] : nums) {
auto [f, s] = vx;
//cout << f << " " << s <<"\n";
if (f == 1) {
seg.add(-N, -s, 0, 0);
seg.add(-s, N, 0, 1);
} else {
seg.add(s, N, 0, 1);
seg.add(-N, s, 0, 0);
}
}
k = seg.query(-N, N) - N;
seg.clear();
}
for (auto [x, vx] : nums) {
ans[x] = k * vx.first + vx.second;
}
//cout << i << " " << can << " " << k << "\n";
}
}
cout << "YES\n";
for (int i = 0 ; i < n ; i++) {
cout << fixed << setprecision(6) << ans[i] << " ";
}
cout << "\n";
}
Compilation message
Graph.cpp: In function 'void dfs(long long int, long long int)':
Graph.cpp:65:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
65 | auto [f, s] = v[x];
| ^
Graph.cpp:66:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
66 | for (auto [i, c] : G[x]) {
| ^
Graph.cpp:77:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
77 | auto [f2, s2] = v[i];
| ^
Graph.cpp: In function 'int main()':
Graph.cpp:123:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
123 | for (auto [x, vx] : nums) {
| ^
Graph.cpp:124:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
124 | auto [f, s] = vx;
| ^
Graph.cpp:137:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
137 | for (auto [x, vx] : nums) {
| ^
Graph.cpp:134:26: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
134 | k = seg.query(-N, N) - N;
| ~~~~~~~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1624 KB |
answer = YES |
| 2 |
Correct |
1 ms |
1628 KB |
answer = YES |
| 3 |
Correct |
1 ms |
1628 KB |
answer = YES |
| 4 |
Incorrect |
1 ms |
1628 KB |
Sum of endpoints for edge (1; 2) differs from the expected value 2. |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1624 KB |
answer = YES |
| 2 |
Correct |
1 ms |
1628 KB |
answer = YES |
| 3 |
Correct |
1 ms |
1628 KB |
answer = YES |
| 4 |
Incorrect |
1 ms |
1628 KB |
Sum of endpoints for edge (1; 2) differs from the expected value 2. |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1624 KB |
answer = YES |
| 2 |
Correct |
1 ms |
1628 KB |
answer = YES |
| 3 |
Correct |
1 ms |
1628 KB |
answer = YES |
| 4 |
Incorrect |
1 ms |
1628 KB |
Sum of endpoints for edge (1; 2) differs from the expected value 2. |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1624 KB |
answer = YES |
| 2 |
Correct |
1 ms |
1628 KB |
answer = YES |
| 3 |
Correct |
1 ms |
1628 KB |
answer = YES |
| 4 |
Incorrect |
1 ms |
1628 KB |
Sum of endpoints for edge (1; 2) differs from the expected value 2. |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1624 KB |
answer = YES |
| 2 |
Correct |
1 ms |
1628 KB |
answer = YES |
| 3 |
Correct |
1 ms |
1628 KB |
answer = YES |
| 4 |
Incorrect |
1 ms |
1628 KB |
Sum of endpoints for edge (1; 2) differs from the expected value 2. |
| 5 |
Halted |
0 ms |
0 KB |
- |
