Submission #1101936

#TimeUsernameProblemLanguageResultExecution timeMemory
1101936crafticatGraph (BOI20_graph)C++17
0 / 100
1089 ms336 KiB
#include "bits/stdc++.h" using namespace std; template<typename T> using V = vector<T>; using vi = V<int>; using vvi = V<vi>; using pi = pair<int,int>; using vpi = V<pi>; #define F0R(i, n) for(int i = 0; i < n;i++) #define FOR(i,a, n) for(int i = a; i < n;i++) #define pb push_back V<bool> vis; V<int> nodes; double determine = -1; bool determineInit = false, possible = true; V<vpi> g; double ep = 0.000000001; struct info { int a, m; bool init = false; info() { } info(int a, int m) : a(a), m(m) { init = true; } bool operator==(info other) const { return a == other.a && m == other.m; } bool operator!=(info other) { return !(a == other.a && m == other.m); } info operator-(info other) const { return {a - other.a,m- other.m}; } double eval(double x) { return a + m * x; } }; V<info> dat; V<double> ans; void calc(int a, int b, int edge) { auto d2 = info(edge,0) - dat[b]; if (dat[a].m == d2.m && dat[a].a == d2.a) return; if (dat[a].m == d2.m && dat[a].a != d2.a) { possible = false; return; } double results = (dat[a].a - d2.a) / ((double) d2.m - dat[a].m); if (determineInit && abs(results - determine) > ep) possible = false; else { determine = results; determineInit = true; } } void solve(int x, int edge, int par) { nodes.pb(x); vis[x] = true; if (par == -1) dat[x] = info(0,1); else { dat[x] = info(edge, 0) - dat[par]; } for (auto &[v,cost] : g[x]) { if (vis[v]) { if (dat[v].init) calc(v, x, cost); continue; } solve(v, cost, x); } } double eval(double x) { double result = 0; for (auto v : nodes) { result += abs(dat[v].eval(x)); } return result; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; g.resize(n + 1); F0R(i, m) { int a, b, c; cin >> a >> b >> c; g[a].pb({b,c}); g[b].pb({a,c}); } vis.resize(n + 1); dat.resize(n + 1); ans.resize(n + 1); FOR(i, 1, n + 1) { if (vis[i]) continue; solve(i, -1, -1); if (!possible) { cout << "NO\n"; return 0; } if (!determineInit) { // Binary search results double l = -1e9, r = 1e9; while (r > l + ep) { double mid = l + (r - l + ep) / 2; if (eval(mid + ep) < eval(mid)) { l = mid + ep; } else { r = mid; } } determine = l; } for (auto x : nodes) ans[x] = dat[x].eval(determine); determine = -1; possible = true; determineInit = false; nodes.clear(); } cout << "YES\n"; FOR(i, 1, n + 1) { cout << fixed << setprecision(6) << ans[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...