Submission #604884

#TimeUsernameProblemLanguageResultExecution timeMemory
604884OttoTheDinoGraph (BOI20_graph)C++17
0 / 100
2 ms2644 KiB
#include <bits/stdc++.h> using namespace std; #define rep(i,s,e) for (int i = s; i <= e; ++i) #define rrep(i,s,e) for (int i = s; i >= e; --i) #define pb push_back #define pf push_front #define all(a) a.begin(), a.end() #define len(a) (int)a.size() #define fi first #define se second typedef long long ll; typedef pair<int,int> ii; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<ii> vii; typedef vector<pll> vpll; const int mx = 1e5; const double eps = 1e-9; vii adj[mx+1]; int b1[mx+1], b2[mx+1], b3[mx+1], c[mx+1]; double ans[mx+1]; vi cur; double eq (double x, double y) { return abs(x-y)<eps; } pair<int,double> dfs1 (int u, int p) { b1[u] = 1; for (ii ve : adj[u]) { int v = ve.fi, e = ve.se; if (e==p) continue; if (b1[v]) { if (u==v) return {u,{c[e]/2.0}}; return {v,c[e]}; } pair<int,double> res = dfs1 (v,e); if (res.fi) { res.se = c[e]-res.se; if (u==res.fi) return {u,res.se/2.0}; return {res.fi,res.se}; } } return {0,0}; } int dfs_help (int u, int d) { int res = d; b3[u] = b1[u] = 1; cur.pb(u); for (ii ve : adj[u]) { int v = ve.fi; if (b3[v]) continue; res = max(res, dfs_help (v,d+1)); } return res; } double dfs2 (int u, int p, double val) { double s = abs(val); b2[u] = 1; ans[u] = val; for (ii ve : adj[u]) { int v = ve.fi, e = ve.se; if (e==p) continue; if (b2[v]) { if (!eq(c[e],val+ans[v])) return 1e9; continue; } double res = dfs2 (v, e, c[e]-val); if (res==1e9) return 1e9; s += res; } return s; } int main () { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; ii edges[m+1]; rep (i,1,m) { int u, v; cin >> u >> v; adj[u].pb({v,i}); adj[v].pb({u,i}); cin >> c[i]; edges[i] = {u,v}; } bool suc = 1; rep (i,1,n) { if (!b1[i]) { pair<int,double> res = dfs1 (i,0); int dep = dfs_help(i,1); if (res.fi) { if (dfs2 (i,-1,res.se)==1e9) { suc = 0; break; } } else { double mis[8*dep+1]; int id = 0; rep (j,0,8*dep) { mis[j] = dfs2 (i,-1,j-4*dep); if (mis[j]<mis[id]) id =j; for (int el : cur) b2[el] = 0; } dfs2(i,-1,id-2*dep); } cur.clear(); } } if (suc) { cout << "YES\n"; rep (i,1,n) cout << ans[i] << " \n"[i==n]; } else cout << "NO\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...