Submission #973931

#TimeUsernameProblemLanguageResultExecution timeMemory
973931NotLinuxGraph (BOI20_graph)C++17
17 / 100
2 ms5228 KiB
//author : FatihCihan #include <bits/stdc++.h> using namespace std; #define all(v) v.begin() , v.end() #define sz(a) (int)a.size() #define int long long #define double long double const int N = 1e5 + 7; const int inf = 1e9 + 7; const double EPS = 0.000000001; const double INF = 1e9 + 7; int n,m; vector < pair < int , int > > graph[N]; pair < int , int > mem[N];//ax + b int par[N]; int find(int a){ if(par[a] == a)return a; return par[a] = find(par[a]); } void merge(int a , int b){ par[find(a)] = find(b); } void solve(){ cin >> n >> m; iota(par , par + n + 1 , 0); for(int i = 0;i<=n;i++)mem[i] = {inf , inf}; for(int i = 0;i<m;i++){ int a,b,c; cin >> a >> b >> c; graph[a].push_back({b , c}); graph[b].push_back({a , c}); merge(a,b); } int cnt_soln[n+1]; memset(cnt_soln , 0 , sizeof(cnt_soln)); double soln[n+1]; set < int > roots; vector < int > components[n+1]; for(int i = 1;i<=n;i++){ roots.insert(find(i)); components[find(i)].push_back(i); } queue < pair < int , pair < int , int > > > q; for(auto itr : roots){ q.push({itr , {1 , 0}}); } while(sz(q)){ int node = q.front().first; pair < int , int > eq = q.front().second; q.pop(); if(mem[node] != pair < int , int >{inf , inf}){// check whether it matches or not if(mem[node].first == eq.first and mem[node].second != eq.second){ cout << "NO" << endl; return; } else if(mem[node].first == eq.first){ 37; } else{ if(cnt_soln[find(node)]){ double mysoln = (double)(mem[node].second - eq.second) / (double)(eq.first - mem[node].first); if(abs(soln[find(node)] - mysoln) > EPS)cnt_soln[find(node)]++; } else{ cnt_soln[find(node)]++; soln[find(node)] = (double)(mem[node].second - eq.second) / (double)(eq.first - mem[node].first); } } } else{ mem[node] = eq; // cout << "node " << node << " : " << eq.first << " " << eq.second << endl; for(auto itr : graph[node]){ q.push({itr.first , {-eq.first , itr.second - eq.second}}); } } } double ans[n+1]; for(auto itr : roots){ if(cnt_soln[itr] > 1){ cout << "NO" << endl; return; } else if(cnt_soln[itr] == 1){ for(auto i : components[itr]){ ans[i] = mem[i].first * soln[itr] + mem[i].second; } } else{ auto check = [&](double x){ double ret = 0; for(auto i : components[itr]){ ret += abs((double)mem[i].first * x + (double)mem[i].second); } return ret; }; double l = 0 , r = INF; while(abs(l - r) > EPS){ double mid = (l + r) / 2; if(check(mid) < check(mid + EPS)){ r = mid; } else{ l = mid + EPS; } } for(auto i : components[itr]){ ans[i] = mem[i].first * l + mem[i].second; } } } cout << "YES" << endl; for(int i = 1;i<=n;i++)cout << fixed << setprecision(6) << ans[i] << " "; cout << endl; } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0); int testcase = 1;//cin >> testcase; while(testcase--)solve(); cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl; }

Compilation message (stderr)

Graph.cpp: In function 'void solve()':
Graph.cpp:62:5: warning: statement has no effect [-Wunused-value]
   62 |     37;
      |     ^~
#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...