aniervs

BOI2020_problem2A

Jul 23rd, 2020
302
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef long double db;
  6. typedef pair<int,int> edge;
  7. typedef pair<ll,ll> node;
  8. const int maxn = 200001;
  9. bool vis[maxn];
  10. node val[maxn];
  11. db ans[maxn];
  12. vector<edge>G[maxn];
  13.  
  14. bool flag, found;
  15. node x;
  16. const db eps = 1e-8;
  17. vector<int> cur;
  18.  
  19. void dfs(int u, int p){
  20.     vis[u] = 1;
  21.     cur.push_back(u);
  22.     for(auto v:G[u]){
  23.         if(v.first == p) continue;
  24.         node t = {val[u].first * -1ll, v.second - val[u].second};
  25.         if(!vis[v.first]){
  26.             val[v.first] = t;
  27.             dfs(v.first, u);
  28.         } else{
  29.             if(t.first == val[v.first].first){
  30.                 if(t.second != val[v.first].second){
  31.                     flag = false;
  32.                     return;
  33.                 }
  34.             } else{
  35.                 node tx = {t.first - val[v.first].first, val[v.first].second - t.second};
  36.                 if(!found) x = tx, found = 1;
  37.                 else if(x.first * tx.second != x.second * tx.first){
  38.                         flag = false;
  39.                         return;
  40.                     }
  41.             }
  42.         }
  43.     }
  44. }
  45.  
  46. db f(db xx){
  47.     db res = 0;
  48.     for(int u:cur)
  49.         res += fabs(xx * (db)val[u].first + (db)val[u].second);
  50.     return res;
  51. }
  52.  
  53. int main() {
  54.     ios_base::sync_with_stdio(0); cin.tie(0);
  55.     cout.setf(ios::fixed); cout.precision(7);
  56.  
  57.     int n, m;
  58.     cin >> n >> m;
  59.     while(m--){
  60.         int u, v, c;
  61.         cin >> u >> v >> c;
  62.         G[u].push_back({v,c});
  63.         G[v].push_back({u,c});
  64.     }
  65.  
  66.     flag = true;
  67.     for(int i = 1; i <= n && flag; i++)
  68.     if(!vis[i]){
  69.         val[i] = {1,0};
  70.         found = false;
  71.         cur.clear();
  72.         dfs(i,-1);
  73.         db xx = 0;
  74.         if(found)
  75.             xx = (db)x.second/(db)x.first;
  76.         else{
  77.             db l = -100000000, r = 100000000;
  78.             while(fabs(r - l) > eps){
  79.                 db m1 = l + (r-l)/(db)3;
  80.                 db m2 = r - (r-l)/(db)3;
  81.                 if(f(m1) > f(m2))
  82.                     l = m1;
  83.                 else
  84.                     r = m2;
  85.             }
  86.             xx = l;
  87.         }
  88.         for(int u:cur)
  89.             ans[u] = xx * (db)val[u].first + (db)val[u].second;
  90.        
  91.     }
  92.  
  93.     if(!flag){
  94.         cout << "NO";
  95.         return 0;
  96.     }
  97.  
  98.     cout << "YES\n";
  99.     for(int i = 1; i <= n; i++)
  100.         cout << ans[i] << ' ';
  101.    
  102.     return 0;
  103. }
  104.  
RAW Paste Data