Submission #1030611

#TimeUsernameProblemLanguageResultExecution timeMemory
1030611ttamxGraph (BOI20_graph)C++17
100 / 100
132 ms20172 KiB
#include<bits/stdc++.h> using namespace std; using db = long double; using ll = long long; const db EPS=1e-12; const db INVPHI=(sqrt(db(5))-1)/2; int main(){ cin.tie(nullptr)->sync_with_stdio(false); int n,m; cin >> n >> m; vector<vector<pair<int,int>>> adj(n); for(int i=0;i<m;i++){ int u,v,w; cin >> u >> v >> w; u--,v--; adj[u].emplace_back(v,w); adj[v].emplace_back(u,w); } vector<bool> vis(n); vector<ll> a(n),b(n); vector<int> comp; pair<ll,ll> val; bool found=false; function<void(int)> dfs=[&](int u){ comp.emplace_back(u); vis[u]=true; for(auto [v,w]:adj[u]){ if(!vis[v]){ a[v]=-a[u]; b[v]=w-b[u]; dfs(v); }else{ if(a[u]+a[v]==0){ if(b[u]+b[v]!=w){ cout << "NO",exit(0); } }else{ ll num=w-b[u]-b[v]; ll den=a[u]+a[v]; if(!found){ found=true; val={num,den}; }else if(num*val.second!=val.first*den){ cout << "NO",exit(0); } } } } }; vector<db> ans(n); for(int i=0;i<n;i++)if(!vis[i]){ comp.clear(); found=false; a[i]=1,b[i]=0; dfs(i); auto calc=[&](db x){ db res=0.0; for(auto u:comp){ ans[u]=a[u]*x+b[u]; res+=abs(ans[u]); } return res; }; if(found){ db x=db(val.first)/db(val.second); calc(x); }else{ db m=comp.size(); db l=-m,r=m; while(r-l>EPS){ db s=(r-l)*INVPHI; db l2=r-s,r2=l+s; if(calc(l2)<calc(r2))r=r2; else l=l2; } calc((l+r)/2.0); } } cout << fixed << setprecision(10); cout << "YES\n"; for(auto x:ans)cout << x << " "; }
#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...