#include <bits/stdc++.h>
template <class T>
using Vec = std::vector<T>;
int main() {
int N, M;
std::cin >> N >> M;
Vec<int> A(M), B(M), C(M);
Vec<Vec<std::pair<int, int>>> graph(N);
for (int i = 0; i < M; ++i) {
std::cin >> A[i] >> B[i] >> C[i];
A[i] -= 1;
B[i] -= 1;
graph[A[i]].emplace_back(B[i], C[i]);
graph[B[i]].emplace_back(A[i], C[i]);
}
Vec<bool> done(N);
Vec<std::pair<int, int>> coeff(N);
Vec<double> val(N);
Vec<int> visited;
auto dfs = [&](auto&& dfs, const int u) -> void {
done[u] = true;
visited.push_back(u);
for (const auto [v, c]: graph[u]) {
if (!done[v]) {
coeff[v].first = -coeff[u].first;
coeff[v].second = c - coeff[u].second;
dfs(dfs, v);
}
}
};
for (int src = 0; src < N; ++src) {
if (!done[src]) {
coeff[src].first = 1;
coeff[src].second = 0;
dfs(dfs, src);
bool sole = false;
Vec<int> pts;
for (const auto u: visited) {
pts.push_back(coeff[u].first * coeff[u].second);
for (const auto [v, c]: graph[u]) {
if (coeff[u].first == coeff[v].first) {
val[src] = (double) (c - coeff[u].second - coeff[v].second) / (coeff[u].first + coeff[v].first);
sole = true;
}
}
}
if (!sole) {
std::sort(pts.begin(), pts.end());
val[src] = pts[pts.size() / 2];
}
for (const auto u: visited) {
if (u != src) {
val[u] = val[src] * coeff[u].first + coeff[u].second;
}
}
visited.clear();
}
}
for (int i = 0; i < M; ++i) {
if (std::abs((val[A[i]] + val[B[i]]) - C[i]) >= 1e-6) {
std::cout << "NO\n";
return 0;
}
}
std::cout << "YES\n";
for (int i = 0; i < N; ++i) {
std::cout << (double) val[i] << " \n"[i + 1 == N];
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
208 KB |
answer = YES |
2 |
Correct |
1 ms |
204 KB |
answer = YES |
3 |
Correct |
1 ms |
204 KB |
answer = YES |
4 |
Correct |
1 ms |
204 KB |
answer = NO |
5 |
Correct |
1 ms |
204 KB |
answer = YES |
6 |
Incorrect |
1 ms |
208 KB |
participant answer is larger than the answer of jury |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
208 KB |
answer = YES |
2 |
Correct |
1 ms |
204 KB |
answer = YES |
3 |
Correct |
1 ms |
204 KB |
answer = YES |
4 |
Correct |
1 ms |
204 KB |
answer = NO |
5 |
Correct |
1 ms |
204 KB |
answer = YES |
6 |
Incorrect |
1 ms |
208 KB |
participant answer is larger than the answer of jury |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
208 KB |
answer = YES |
2 |
Correct |
1 ms |
204 KB |
answer = YES |
3 |
Correct |
1 ms |
204 KB |
answer = YES |
4 |
Correct |
1 ms |
204 KB |
answer = NO |
5 |
Correct |
1 ms |
204 KB |
answer = YES |
6 |
Incorrect |
1 ms |
208 KB |
participant answer is larger than the answer of jury |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
208 KB |
answer = YES |
2 |
Correct |
1 ms |
204 KB |
answer = YES |
3 |
Correct |
1 ms |
204 KB |
answer = YES |
4 |
Correct |
1 ms |
204 KB |
answer = NO |
5 |
Correct |
1 ms |
204 KB |
answer = YES |
6 |
Incorrect |
1 ms |
208 KB |
participant answer is larger than the answer of jury |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
208 KB |
answer = YES |
2 |
Correct |
1 ms |
204 KB |
answer = YES |
3 |
Correct |
1 ms |
204 KB |
answer = YES |
4 |
Correct |
1 ms |
204 KB |
answer = NO |
5 |
Correct |
1 ms |
204 KB |
answer = YES |
6 |
Incorrect |
1 ms |
208 KB |
participant answer is larger than the answer of jury |
7 |
Halted |
0 ms |
0 KB |
- |