Submission #932266

#TimeUsernameProblemLanguageResultExecution timeMemory
932266Jawad_Akbar_JJGraph (BOI20_graph)C++17
0 / 100
5 ms15196 KiB
#include <iostream> #include <vector> #include <iomanip> #include <map> using namespace std; #define ld long double const int N = 2e5 + 10; vector<vector<int>> nei[N]; int l[N],r[N],c[N]; ld a[N],b[N],inf = 1e9,ans[N]; int pen[100]; int seen[N]; map<pair<int,int>,int> mp; int T = 1; void dfs1(int u,int p = 0,int v = 0,int last = 0){ if (v >= 10){ last += pen[v]; if (a[u] != inf){ if (a[u] != last){ cout<<"NO\n"; exit(0); } return; } a[u] = last; v = 0; } v *= 10; for (auto i : nei[u]){ if (i[0] == p) continue; dfs1(i[0],u,v + i[1],last); } } void dfs2(int u,int p = 0,int v = 0,int last = 0){ if (v >= 10){ last += pen[v]; if (b[u] != inf){ if (b[u] != last){ cout<<"NO\n"; exit(0); } return; } b[u] = last; v = 0; } v *= 10; for (auto i : nei[u]){ if (i[0] == p) continue; dfs2(i[0],u,v + i[1],last); } } ld k; void dfs3(int u){ for (auto i : nei[u]){ if (ans[i[0]] != inf) continue; ans[i[0]] = i[1] - ans[u]; dfs3(i[0]); } } vector<int> vec,vv; void get(int u){ seen[u] = true; vv.push_back(u); for (auto v : nei[u]){ if (seen[v[0]]) continue; vec.push_back({v[2]}); get(v[0]); } } ld calc(ld v){ ld ans = 0; for (int i : vv){ if (a[i] != inf) ans += abs(v + a[i]); else ans += abs(k - v + b[i]); } return ans; } signed main(){ cout<<fixed<<setprecision(9); int n,m; cin>>n>>m; pen[21] = -1; pen[12] = +1; for (int i=1;i<=n;i++) a[i] = b[i] = ans[i] = inf; int cur = 1; for (int i=1;i<=m;i++){ int u,v,t; cin>>u>>v>>t; if (mp[{u,v}] != 0){ if (mp[{u,v}] == t) continue; cout<<"NO"<<endl; exit(0); } l[cur] = u; r[cur] = v; c[cur] = t; cur++; nei[u].push_back({v,t,i}); nei[v].push_back({u,t,i}); mp[{u,v}] = mp[{v,u}] = t; } m = cur - 1; for (int i=1;i<=n;i++){ if (seen[i] or nei[i].size() == 0) continue; vec.clear(); vv.clear(); get(i); bool con = false; for (int j : vec) if (l[j] == r[j]){ ans[l[j]] = c[j] / 2.0; dfs3(l[j]); con = true; break; } if (con) continue; a[i] = 0; dfs1(i); int u = nei[i][0][0]; if (a[u] != inf){ ld A = nei[i][0][1] - a[u]; A = A / 2.0; ans[i] = A; dfs3(i); continue; } dfs2(u); k = nei[i][0][1]; ld lft = -1e5,rgt = nei[i][0][1]; while (rgt - lft > 0.00000001){ ld mid = (lft + rgt)/2.0; ld frst = calc(mid); ld sec = calc(mid + 0.00000001); if (frst < sec) rgt = mid; else lft = mid; } ans[i] = lft; dfs3(i); } for (int i=1;i<=n;i++) if (ans[i] == inf) ans[i] = 0; for (int i=1;i<=m;i++){ if (abs(c[i] - ans[l[i]] - ans[r[i]]) > 0.0000001){ cout<<"NO"<<endl; return 0; } } cout<<"YES"<<endl; for (int i=1;i<=n;i++) cout<<ans[i]<<" "; cout<<endl; }
#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...