Submission #970934

#TimeUsernameProblemLanguageResultExecution timeMemory
970934maxFedorchukGraph (BOI20_graph)C++17
0 / 100
2 ms9268 KiB
#include <bits/stdc++.h> using namespace std; const long long MX=2e5+10,INF=1e18; vector < pair < long long , long long > > mas[MX]; pair < long long , long double > cnt[MX]; long double ans[MX],vis[MX]; vector < long long > vr; void DFS(long long zar) { vis[zar]=1; vr.push_back(zar); for(auto [u,zn]:mas[zar]) { if(!vis[u]) { cnt[u]=make_pair(-cnt[zar].first,zn-cnt[zar].second); DFS(u); } } } void cntans() { long double x=-INF,nwx; for(auto u:vr) { for(auto [a,b]:mas[u]) { if(cnt[u].first==0 || cnt[u].first!=cnt[a].first) { if(cnt[u].second+cnt[a].second!=b) { cout<<"NO\n"; exit(0); } } else { nwx=(b-cnt[u].second-cnt[a].second)/(2*cnt[u].first); if(x==-INF) { x=nwx; } if(x!=nwx) { cout<<"NO\n"; exit(0); } } } } if(x==-INF) { vector < long double > o; for(auto u:vr) { o.push_back(cnt[u].second); } sort(o.begin(),o.end()); x=o[o.size()/2]; } for(auto u:vr) { ans[u]=cnt[u].first*x+cnt[u].second; } } void vip1(long long a,long long k) { vr.clear(); cnt[a]=make_pair(0,((k==1)?(0.5):1)); DFS(a); cntans(); } void vip2(long long a) { vr.clear(); cnt[a]=make_pair(1,0); DFS(a); cntans(); } int main() { //cin.tie(0); //ios_base::sync_with_stdio(0); long long n,m; cin>>n>>m; fill(ans+1,ans+1+n,-INF); vector < pair < long long ,long long > > vc; for(long long i=1;i<=m;i++) { long long a,b,c; cin>>a>>b>>c; mas[a].push_back({b,c}); mas[b].push_back({a,c}); if(a==b) { vc.push_back({a,c}); } } for(auto u:vc) { if(ans[u.first]==-INF) { vip1(u.first,u.second); } } for(long long i=1;i<=n;i++) { if(ans[i]==-INF) { vip2(i); } } cout<<"YES\n"; for(long long i=1;i<=n;i++) { 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...