Submission #1180823

#TimeUsernameProblemLanguageResultExecution timeMemory
1180823julia_08Graph (BOI20_graph)C++20
0 / 100
1 ms2632 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 10; int marc[MAXN], a[MAXN], b[MAXN]; double val[MAXN]; vector<pair<int, int>> adj[MAXN]; vector<int> comp; double x; bool ok; void dfs(int v){ marc[v] = 1; comp.push_back(v); for(auto [u, w] : adj[v]){ if(!marc[u]){ a[u] = -a[v], b[u] = w - b[v]; dfs(u); } else{ if(a[u] + a[v] != 0){ x = ((double) (w - b[u] - b[v])) / ((double) (a[u] + a[v])); ok = false; } } } } int main(){ cin.tie(0)->sync_with_stdio(0); int n, m; cin >> n >> m; for(int i=1; i<=m; i++){ int a, b, c; cin >> a >> b >> c; adj[a].push_back({b, c}); adj[b].push_back({a, c}); } for(int i=1; i<=n; i++){ if(!marc[i]){ comp.clear(); ok = true; a[i] = 1, b[i] = 0; dfs(i); if(ok){ vector<int> median; for(auto j : comp){ if(a[j] > 0) median.push_back(-b[j]); if(a[j] < 0) median.push_back(b[j]); } sort(median.begin(), median.end()); x = (double) median[(int) median.size() / 2]; } for(auto j : comp) val[j] = a[j] * x + b[j]; } } for(int i=1; i<=n; i++){ for(auto [j, w] : adj[i]){ if(val[i] + val[j] - w > 1e-6){ cout << "NO\n"; return 0; } } } cout << "YES\n"; cout << fixed << setprecision(6); for(int i=1; i<=n; i++) cout << val[i] << " "; cout << "\n"; 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...