Submission #781141

#TimeUsernameProblemLanguageResultExecution timeMemory
781141FEDIKUSGraph (BOI20_graph)C++17
5 / 100
3 ms2656 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; const ll maxn=1e5+10; vector<pair<ll,ll> > g[maxn]; bool moze=true; bool vis[maxn]; ll val[maxn]; ll sgn[maxn]; double res[maxn]; vector<int> comp; set<ll> a; void dfs(ll node){ comp.push_back(node); vis[node]=true; for(auto i:g[node]){ if(vis[i.first]){ if(sgn[i.first]!=sgn[node] && val[i.first]+val[node]!=i.second) moze=false; if(sgn[i.first]==sgn[node]){ if(sgn[i.first]==1) a.emplace(i.second-val[node]-val[i.first]); else a.emplace(val[i.first]+val[node]-i.second); } }else{ sgn[i.first]=-sgn[node]; val[i.first]=i.second-val[node]; dfs(i.first); } } } ll range(int l,int r,vector<ll> &arr){ return arr[r]-(l>0 ? arr[l-1]:0); } int main(){ ll n,m; cin>>n>>m; for(ll i=0;i<m;i++){ ll u,v,c; cin>>u>>v>>c; g[u].push_back({v,c}); g[v].push_back({u,c}); } for(int i=1;i<=n;i++){ if(vis[i]) continue; sgn[i]=1; val[i]=0; comp.clear(); a.clear(); dfs(i); if(a.size()>1) moze=false; if(a.size()==1){ double aa=*a.begin(); for(ll i:comp){ res[i]=aa*sgn[i]/2+val[i]; } continue; } pair<ll,int> best={LLONG_MAX,0}; vector<int> kandidati; for(ll i:comp) kandidati.push_back(-val[i]*sgn[i]); sort(kandidati.begin(),kandidati.end()); vector<int> poz; vector<int> neg; for(int i:comp){ if(sgn[i]>0) poz.push_back(val[i]); else neg.push_back(val[i]); } vector<ll> prefpoz; vector<ll> prefneg; partial_sum(poz.begin(),poz.end(),back_inserter(prefpoz)); partial_sum(neg.begin(),neg.end(),back_inserter(prefneg)); int ipoz=0; int ineg=0; for(int i:kandidati){ while(ipoz<poz.size() && poz[ipoz]+i>=0) ipoz++; while(ineg<neg.size() && neg[ineg]-i<=0) ineg++; ll sum=0; sum-=(ipoz>0 ? prefpoz[ipoz-1]:0)+ipoz*i; sum+=(ipoz!=poz.size() ? range(ipoz,poz.size()-1,prefpoz):0)+(poz.size()-ipoz)*i; sum+=(ineg>0 ? prefneg[ineg-1]:0)+ineg*i; sum-=(ineg!=neg.size() ? range(ineg,neg.size()-1,prefneg):0)+(neg.size()-ineg)*i; best=min(best,{sum,i}); } for(ll i:comp){ res[i]=val[i]+best.second*sgn[i]; } } if(moze){ cout<<"YES\n"; cout<<fixed<<showpoint<<setprecision(15); for(int i=1;i<=n;i++){ cout<<res[i]; cout<<" "; } }else cout<<"NO\n"; return 0; }

Compilation message (stderr)

Graph.cpp: In function 'int main()':
Graph.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |             while(ipoz<poz.size() && poz[ipoz]+i>=0) ipoz++;
      |                   ~~~~^~~~~~~~~~~
Graph.cpp:90:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |             while(ineg<neg.size() && neg[ineg]-i<=0) ineg++;
      |                   ~~~~^~~~~~~~~~~
Graph.cpp:95:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |             sum+=(ipoz!=poz.size() ? range(ipoz,poz.size()-1,prefpoz):0)+(poz.size()-ipoz)*i;
      |                   ~~~~^~~~~~~~~~~~
Graph.cpp:98:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |             sum-=(ineg!=neg.size() ? range(ineg,neg.size()-1,prefneg):0)+(neg.size()-ineg)*i;
      |                   ~~~~^~~~~~~~~~~~
#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...