Submission #1052149

#TimeUsernameProblemLanguageResultExecution timeMemory
1052149duckindogGraph (BOI20_graph)C++17
0 / 100
1 ms3164 KiB
#include <bits/stdc++.h> using namespace std; const int N = 100'000 + 10, MAX = 1'000'000'000; int n, m; vector<pair<int, int>> ad[N]; int a[N]; int32_t main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m; for (int i = 1; i <= m; ++i) { int u, v, w; cin >> u >> v >> w; w *= 10; ad[u].push_back({v, w}); ad[v].push_back({u, w}); } auto cal = [&](int x) { memset(a, -1, sizeof a); a[1] = x; queue<int> q({1}); int ret = 0; while (q.size()) { auto u = q.front(); q.pop(); ret += abs(a[u]); for (const auto& [v, w] : ad[u]) { if (a[v] == -1) { a[v] = w - a[u]; q.push(v); } if (w - a[u] != a[v]) return MAX; } } return ret; }; int st = -1; int answer = MAX; for (int x = -5; x <= 20; x += 5) { int value = cal(x); if (answer > value) { answer = value; st = x; } } if (st == -1) { cout << "NO" << "\n"; return 0; } cal(st); cout << "YES" << "\n"; for (int i = 1; i <= n; ++i) cout << a[i] / 10 << "." << a[i] % 10 << " "; cout << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...