Submission #1065657

#TimeUsernameProblemLanguageResultExecution timeMemory
1065657Rawlat_vanakGraph (BOI20_graph)C++17
100 / 100
98 ms25564 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define speedIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define mod 1000000007 #define f first #define s second #define pii pair<int,int> #define pb push_back vector<vector<pii>> graph; vector<pair<int,float>> value; vector<bool> visited; vector<int> conectedcomp; bool possible; float thex; void dfs(int u){ if(visited[u]) return; visited[u]=true; conectedcomp.pb(u); //cout<<u<<'\n'; for(auto x:graph[u]){ int v=x.f; int c=x.s; //cout<<"hi "<<u<<' '<<v<<'\n'; if(visited[v]){ if(value[u].f==-value[v].f){ if(value[u].s!=c-value[v].s){ possible=false; } }else{ //cout<<"buhhuuhuh "<<u<<' '<<v<<'\n'; float tmp=c-value[u].s-value[v].s; tmp/=(value[v].f+value[u].f); if(thex==1e10){ thex=tmp; }else if(thex!=tmp){ possible=false; } value[u]={0,tmp*(value[u].f)+value[u].s}; value[v]={0,tmp*(value[v].f)+value[v].s}; } }else{ value[v]={-value[u].f,c-value[u].s}; dfs(v); } } } int32_t main(){ speedIO; int t,n,m,k; //cin>>t; t=1; while(t--){ //string s; cin>>n>>m; graph.resize(n+1); value.resize(n+1); conectedcomp.clear(); visited.resize(n+1,false); possible=true; thex=1e10; for(int i=0;i<m;i++){ int a,b,c; cin>>a>>b>>c; if(a==b){ value[a]={0,c/2}; } graph[a].pb({b,c}); graph[b].pb({a,c}); } //value[1]={1,0}; //dfs(1); vector<float> ans(n+1); for(int i=1;i<=n;i++){ //cout<<value[i].f<<' '<<value[i].s<<'\n'; if(visited[i]==false){ conectedcomp.clear(); thex=1e10; //visited[i]=true; value[i]={1,0}; dfs(i); if(thex!=1e10){ for(int j:conectedcomp){ value[j]={0,thex*(value[j].f)+value[j].s}; //cout<<value[j].s<<' '; ans[j]=(value[j].s); } }else{ vector<float> valss; float yyyy=0; for(int j:conectedcomp){ valss.pb(-(value[j].f)*(value[j].s)); yyyy-=(value[j].f)*(value[j].s); } sort(valss.rbegin(),valss.rend()); float tmp=1e10; int xxxxx=conectedcomp.size(); int idx; for(int l=0;l<conectedcomp.size();l++){ //cout<<xxxxx<<' '<<yyyy<<'\n'; if (tmp>xxxxx*valss[l]-yyyy){ tmp=xxxxx*valss[l]-yyyy; idx=valss[l]; } yyyy-=2*valss[l]; xxxxx-=2; } for(int j:conectedcomp){ ans[j]=idx*(value[j].f)+value[j].s; } } } } if(possible){ cout<<"YES"<<'\n'; for(int i=1;i<=n;i++){ cout<<ans[i]<<' '; } cout<<'\n'; }else{ cout<<"NO"<<'\n'; } } return 0; }

Compilation message (stderr)

Graph.cpp: In function 'int32_t main()':
Graph.cpp:110:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |      for(int l=0;l<conectedcomp.size();l++){
      |                  ~^~~~~~~~~~~~~~~~~~~~
Graph.cpp:56:12: warning: unused variable 'k' [-Wunused-variable]
   56 |  int t,n,m,k;
      |            ^
Graph.cpp:120:17: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  120 |       ans[j]=idx*(value[j].f)+value[j].s;
      |              ~~~^~~~~~~~~~~~~
#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...