Submission #1102659

#TimeUsernameProblemLanguageResultExecution timeMemory
1102659alexddGraph (BOI20_graph)C++17
17 / 100
3 ms10832 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") using namespace std; #define int long long #define double long double const int INF = 1e14; int n,m; double val[100005]; int u[200005],v[200005],s[200005]; vector<pair<int,int>> con[100005]; bool visited[100005]; bool bun; double cur; vector<int> aux; void dfs(int nod) { cur += abs(val[nod]); aux.push_back(nod); visited[nod]=1; for(auto [adj,sum]:con[nod]) { if(!visited[adj]) { val[adj] = sum - val[nod]; dfs(adj); } else if(val[adj] != sum - val[nod]) bun = 0; } } vector<double> possible; bool isbipartit; int parte[100005]; pair<int,int> parent[100005]; int cap1,cap2,scap; void dfs_bipartit(int nod) { for(auto [adj,c]:con[nod]) { if(parte[adj]==-1) { parte[adj] = 1-parte[nod]; parent[adj] = {nod,c}; dfs_bipartit(adj); } else if(parte[adj] != 1-parte[nod]) { isbipartit=0; cap1 = adj; cap2 = nod; scap = c; } } } bool verif_bipartit(int nod) { parte[nod]=0; isbipartit=1; dfs_bipartit(nod); if(!isbipartit) { int cur=cap1; double sum=scap,sum2=0; int pas=0; while(cur!=cap2) { if(pas==0) { sum2 += parent[cur].second; } pas = 1-pas; sum += parent[cur].second; cur = parent[cur].first; } sum/=2; val[cap2] = sum - sum2; bun=1; dfs(cap2); if(!bun) { cout<<"NO"; exit(0); } } return isbipartit; } signed main() { ios_base::sync_with_stdio(0);cin.tie(0); for(double i = -3;i<=3;i+=0.5) possible.push_back(i); cin>>n>>m; for(int i=1;i<=m;i++) { cin>>u[i]>>v[i]>>s[i]; con[u[i]].push_back({v[i],s[i]}); con[v[i]].push_back({u[i],s[i]}); } for(int i=1;i<=n;i++) { parte[i]=-1; visited[i]=0; } for(int i=1;i<=n;i++) { if(!visited[i]) { if(verif_bipartit(i)) { double mnm=INF,unde; for(double x:possible) { val[i] = x; bun=1; aux.clear(); cur=0; dfs(i); if(bun && cur<mnm) { mnm = cur; unde = x; } for(int y:aux) visited[y]=0; } if(mnm==INF) { cout<<"NO"; return 0; } val[i] = unde; dfs(i); } } } cout<<"YES\n"; for(int i=1;i<=n;i++) cout<<val[i]<<" "; return 0; }

Compilation message (stderr)

Graph.cpp: In function 'int main()':
Graph.cpp:132:24: warning: 'unde' may be used uninitialized in this function [-Wmaybe-uninitialized]
  132 |                 val[i] = unde;
      |                 ~~~~~~~^~~~~~
#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...