Submission #1256287

#TimeUsernameProblemLanguageResultExecution timeMemory
1256287JovicaGraph (BOI20_graph)C++20
58 / 100
1094 ms11128 KiB
#include <bits/stdc++.h> using namespace std; int const maxn = 1e5+1; vector<int> ans; vector<vector<array<int,2> > > adj(maxn); int gazda[maxn],vred[maxn][2],k; bool visited[maxn]; int niza[maxn]; void bfs(int g,int k) { int z = 0; queue<array<int,2> > q;queue<int> zima; q.push({g,k}); while (q.size()) { int p = q.front()[0],x = q.front()[1];gazda[p] = g; q.pop(); zima.push(p); for (auto a: adj[p]){ if (visited[a[0]]){ if (vred[a[0]][0] + x != a[1]*2) z = -1e9; continue; } visited[a[0]] = true;vred[a[0]][0] = a[1]*2 - x; z+= abs(vred[a[0]][0]); q.push({a[0],vred[a[0]][0]}); } } if (z<niza[g] && z>= 0){ niza[g] = z; while (zima.size()) { int p = zima.front(); zima.pop(); vred[p][1] = vred[p][0]; } } } int main() {ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); int n,m; cin>>n>>m;for (int i=0;i<=n;i++) niza[i] = 1e9; for (int i=1;i<=m;i++) { int a,b,c; cin>>a>>b>>c; adj[a].push_back({b,c}); adj[b].push_back({a,c}); } vector<int> ulava; for (k=0;k<=400;k++) { memset(visited,0,sizeof(visited)); if (k == 0){ for (int i=1;i<=n;i++) if (visited[i] == false) bfs(i,-200 + k),ulava.push_back(i); } else{ for (auto a: ulava) bfs(a,-200 + k); } } for (int i=1;i<=n;i++) if (niza[gazda[i]] == 1e9) { cout<<"NO\n"; return 0; } cout<<"YES\n"; for (int i=1;i<=n;i++) { double d = vred[i][1]; cout<<d/2<<" "; } 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...