Submission #1145469

#TimeUsernameProblemLanguageResultExecution timeMemory
1145469LudisseyGraph (BOI20_graph)C++17
0 / 100
0 ms324 KiB
#include <bits/stdc++.h> #define sz(a) (int)a.size() #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define int long long using namespace std; vector<pair<bool,double>> val; // le teken de x(false = -1 ||true = 1) et b vector<double> out; double gem=0; double gemC=0; vector<vector<pair<int,int>>> neigh; vector<int> visited; double valeurDOFFICE=1e9; bool possible=true; void dfs(int x, bool tt, double b){ if(visited[x]==1){ if(val[x]==make_pair(tt,b)) return; if(val[x].first==tt) { possible=false; return; } else{ double b1=val[x].second; double b2=b; if(b1==false) swap(b1,b2); valeurDOFFICE=(b1-b2)/(double)2; return; } } visited[x]=1; val[x]={tt,b}; if(tt) gem+=-b; else gem+=b; gemC++; for (auto u : neigh[x]) { dfs(u.first,!tt,u.second-b); if(possible==false||valeurDOFFICE<1e9){ return; } } } void setVAL(int x, double vl){ if(visited[x]==2){ if(abs(vl-out[x])>0.0000001) possible=false; return; }; out[x]=vl; visited[x]=2; for (auto u : neigh[x]) setVAL(u.first,u.second-vl); } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n,m; cin >> n >> m; visited.resize(n,0); neigh.resize(n); out.resize(n); val.resize(n); for (int i = 0; i < m; i++) { int u,v,c; cin >> u >> v >> c; u--; v--; neigh[u].push_back({v,c}); neigh[v].push_back({u,c}); } for (int i = 0; i < n; i++) { if(visited[i]>0) continue; gem=0; gemC=0; valeurDOFFICE=1e9; dfs(i,true,0); if(!possible) break; if(valeurDOFFICE==1e9){ valeurDOFFICE=(gem)/gemC; } setVAL(i,valeurDOFFICE); } if(possible){ cout << "YES\n"; for (int i = 0; i < n; i++) { cout << setprecision(7) << out[i] << " "; } }else{ cout << "NO\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...