Submission #685515

#TimeUsernameProblemLanguageResultExecution timeMemory
685515stanislavpolynGraph (BOI20_graph)C++17
100 / 100
224 ms22512 KiB
#include <bits/stdc++.h> #define fr(i, a, b) for (int i = (a); i <= (b); ++i) #define rf(i, a, b) for (int i = (a); i >= (b); --i) #define fe(x, y) for (auto& x : y) #define fi first #define se second #define pb push_back #define mp make_pair #define mt make_tuple #define all(x) (x).begin(), (x).end() #define sz(x) (int)(x).size() #define pw(x) (1LL << (x)) using namespace std; mt19937_64 rng(228); #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define fbo find_by_order #define ook order_of_key template <typename T> bool umn(T& a, T b) { return a > b ? a = b, 1 : 0; } template <typename T> bool umx(T& a, T b) { return a < b ? a = b, 1 : 0; } using ll = long long; using ld = long double; using pii = pair<int, int>; using pll = pair<ll, ll>; template <typename T> using ve = vector<T>; const int N = 1e5 + 5; const ld EPS = 1e-10; bool eq(ld a, ld b) { return abs(a - b) <= EPS; } int n, m; ve<pii> g[N]; bool vis[N]; int k[N], b[N]; ve<int> st; ld X = -1e18; bool found = 0; ld ans[N]; void dfs(int v, int p) { vis[v] = 1; st.pb(v); // cout << v << " " << k[v] << " " << b[v] << "\n"; fe (to, g[v]) { if (!vis[to.fi]) { b[to.fi] = -b[v] + to.se; k[to.fi] = -k[v]; dfs(to.fi, v); } else { int needB = -b[v] + to.se; int needK = -k[v]; if (mp(b[to.fi], k[to.fi]) == mp(needB, needK)) { continue; } // x * needK + needB = x * k[to.fi] + b[to.fi] // x * (needK - k[to.fi]) = b[to.fi] - needB ld nx = ld(b[to.fi] - needB) / (needK - k[to.fi]); if (found && !eq(nx, X)) { cout << "NO\n"; exit(0); } X = nx; found = 1; } } } int main() { #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #else ios::sync_with_stdio(0); cin.tie(0); #endif cin >> n >> m; fr (i, 1, m) { int a, b, c; cin >> a >> b >> c; g[a].pb({b, c}); g[b].pb({a, c}); } fr (i, 1, n) { if (!vis[i]) { st.clear(); k[i] = 1; X = -1e18; found = 0; dfs(i, 0); if (found) { fe (cur, st) { ans[cur] = k[cur] * X + b[cur]; } } else { auto eval = [&](ld x) { ld sum = 0; fe (cur, st) { sum += abs(k[cur] * x + b[cur]); } return sum; }; fe (cur, st) { assert(k[cur] == 1 || k[cur] == -1); // assert(abs(b[cur]) <= 2); } ld l = -1e9; ld r = 1e9; fr (rep, 1, 200) { ld p1 = l + (r - l) / 3; ld p2 = r - (r - l) / 3; if (eval(p1) < eval(p2)) { r = p2; } else { l = p1; } } fe (cur, st) { ans[cur] = k[cur] * l + b[cur]; } } } } cout << "YES\n"; cout << fixed << setprecision(14); fr (i, 1, n) { cout << ans[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...