Submission #932135

#TimeUsernameProblemLanguageResultExecution timeMemory
932135Muhammad_AneeqGraph (BOI20_graph)C++17
58 / 100
322 ms17916 KiB
/* بسم الله الرحمن الرحيم Author: (:Muhammad Aneeq:) */ #include <iostream> #include <vector> #include <algorithm> using namespace std; int const N=1e5+10; vector<pair<int,int>>nei[N]={}; float val[N]={},ansval[N]={}; bool vis[N]={}; vector<pair<pair<int,int>,int>>ed; float mx=1e9+10; int n,m; vector<vector<int>>f; bool dfs1(int u) { for (auto [i,j]:nei[u]) { if (val[i]==-1e9) { val[i]=j-val[u]; if (dfs1(i)==0) return 0; } else if (val[i]+val[u]!=j) return 0; } return 1; } void dfs(int x) { vis[x]=1; f.back().push_back(x); for (auto [i,j]:nei[x]) { if (!vis[i]) dfs(i); } } inline void solve() { cin>>n>>m; for (int i=0;i<m;i++) { int u,v,t; cin>>u>>v>>t; nei[u].push_back({v,t}); nei[v].push_back({u,t}); if (u>v) swap(u,v); ed.push_back({{u,v},t}); } for (int i=1;i<=n;i++) { if (!vis[i]) { f.push_back({}); dfs(i); } } for (int i=1;i<=n;i++) { val[i]=-1e9; ansval[i]=-1e9; } for (auto i:f) { int r=i[0]; float mx=1e9+10; for (float j=-30;j<=25;j+=0.5) { val[r]=j; if (dfs1(r)) { float z=0; for (auto k:i) z+=abs(val[k]); if (z<mx) { mx=z; for (auto k:i) ansval[k]=val[k]; } } for (auto k:i) val[k]=-1e9; } } for (int i=1;i<=n;i++) { if (ansval[i]==-1e9) { cout<<"NO\n";return; } } cout<<"YES\n"; for (int i=1;i<=n;i++) cout<<ansval[i]<<' '; cout<<endl; } int main() { ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); solve(); }
#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...