Submission #557052

#TimeUsernameProblemLanguageResultExecution timeMemory
557052promaGraph (BOI20_graph)C++17
0 / 100
3 ms2644 KiB
#include <bits/stdc++.h> //#define int long long #define endl "\n" #define see(x) cout<<#x<<"="<<x<<"\n"; using namespace std; const int N = 1e5+5; const int INF = 1e9; int n, m, flag, used[N], val[N], s[N]; vector <pair <int, int>> g[N]; vector <int> visited; double x, res[N]; void dfs(int v, int p = 0) { used[v] = 1; visited.push_back(v); for (auto i: g[v]) { if (i.first == p) continue; if (used[i.first] and s[i.first] == s[v] and x == INF) { x = (i.second - val[i.first] - val[v]) / 2.0; } else if (!used[i.first]) { s[i.first] = -s[v]; val[i.first] = i.second - val[v]; dfs(i.first, v); } } } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); /* freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); */ cin >> n >> m; for (int i = 0; i < m; i ++) { int u, v, w; cin >> u >> v >> w; g[u].push_back({v, w}); g[v].push_back({u, w}); } for (int i = 1; i <= n; i ++) { if (!used[i]) { x = INF; s[i] = 1; val[i] = 0; visited.clear(); dfs(i); if (x == INF) { vector <int> v; for (auto i: visited) { v.push_back(val[i] * (-s[i])); } sort(v.begin(), v.end()); int cnt = v.size(); if (cnt % 2) x = v[cnt/2]; else x = (v[cnt/2] + v[cnt/2+1]) / 2.0; } for (auto i: visited) { res[i] = s[i] * x + val[i]; } } } for (int i = 1; i <= n; i ++) { for (auto j: g[i]) { if (res[i] + res[j.first] != j.second) { cout << "NO\n"; return 0; } } } cout << "YES\n"; for (int i = 1; i <= n; i ++) { cout << res[i] << " "; } return 0; }
#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...