Submission #932267

#TimeUsernameProblemLanguageResultExecution timeMemory
932267UmairAhmadMirzaGraph (BOI20_graph)C++17
5 / 100
1 ms600 KiB
#include <bits/stdc++.h> using namespace std; int const N=105; double const inf=1e9+5; vector<pair<int,int>> adj[N]; double edge[N][N]; vector<int> com[N]; int cc=0; int rep[N]; double X[N]; double ct[N]; double val[N]; int n,m; void cc_find(int node,int xx,int c){ ct[node]=c; X[node]=xx; rep[node]=cc; com[cc].push_back(node); for(auto i:adj[node]) if(rep[i.first]==0) cc_find(i.first,-xx,i.second-c); } double answer(int c,double x){ double v=0.0; for(int i:com[c]) for(int j:com[c]) if(edge[i][j]>0){ v=(X[i]+X[j])*x; v+=ct[i]+ct[j]; if(v!=edge[i][j]) return inf; } double sm=0.0; for(auto i:com[c]) sm+=abs((X[i]*x)+ct[i]); return sm; } int main(){ cin>>n>>m; for(int i=0;i<m;i++){ int u,v,w; cin>>u>>v>>w; adj[u].push_back({v,w}); adj[v].push_back({u,w}); if(edge[u][v]>0 && edge[u][v]!=w){ cout<<"NO"<<endl; return 0; } edge[v][u]=w; edge[u][v]=w; } for(int i=1;i<=n;i++){ if(rep[i]==0){ cc++; cc_find(i,1.0,0.0); } } double ans=0.0; for(int c=1;c<=cc;c++){ double sm=inf; double xx=-3; for(double t=0;t<=40;t++){ double x=-2.0+((0.1)*t); // cout<<x<<endl; if(answer(c,x)<sm){ sm=answer(c,x); xx=x; } } if(sm==inf){ cout<<"NO"<<endl; return 0; } for(auto i:com[c]) val[i]=(X[i]*xx)+ct[i]; } cout<<fixed; cout<<"YES"<<endl; for(int i=1;i<=n;i++) cout<<setprecision(10)<<val[i]<<' '; cout<<endl; // cout<<ans<<endl; }

Compilation message (stderr)

Graph.cpp: In function 'int main()':
Graph.cpp:58:10: warning: unused variable 'ans' [-Wunused-variable]
   58 |   double ans=0.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...