Submission #518786

#	Time	Username	Problem	Language	Result	Execution time	Memory
518786		Wayne_Yan	Graph (BOI20_graph)	C++17	100 / 100	467 ms	37616 KiB

Graph

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
typedef int64_t ll;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb emplace_back
#define mp make_pair
#define mt make_tuple
#define pii pair<int,int>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define RF(n) RFi(i,n)
#define RFi(i,n) RFl(i,0,n)
#define RFl(i,l,n) for(int i=n-1;i>=l;i--)
#define all(v) begin(v),end(v)
#define siz(v) (ll(v.size()))
#define get_pos(v,x) (lower_bound(all(v),x)-begin(v))
#define sort_uni(v) sort(begin(v),end(v)),v.erase(unique(begin(v),end(v)),end(v))
#define mem(v,x) memset(v,x,sizeof v)
#define ff first
#define ss second
#define mid ((l+r)/2)
#define RAN(a,b) uniform_int_distribution<int> (a, b)(rng)
#define debug(x) (cerr << (#x) << " = " << x << "\n")
#define cmax(a,b) (a = max(a,b))
#define cmin(a,b) (a = min(a,b))

template <typename T> using max_heap = __gnu_pbds::priority_queue<T,less<T> >;
template <typename T> using min_heap = __gnu_pbds::priority_queue<T,greater<T> >;
template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;


inline long double f(pii p, long double s){
  return s * p.ff + p.ss;
}

const int maxN = 1e5+10;
vector<pii> edge[maxN];
bool visited[maxN];
vector<pii> curr_poly;
long double eps = 1e-12;
long double val[maxN];


long double sub(long double x){
  long double ans = 0;
  
  pii fin = {0,0};
  for(pii p : curr_poly){
    if(f(p, x) > 0){
      fin.ff += p.ff;
      fin.ss += p.ss;
    }else{
      fin.ff -= p.ff;
      fin.ss -= p.ss;
    }
  }
  ans = fin.ff * x + fin.ss;
  return ans;
}


map<pii, int> chk;

long double ccx = 1e18;

pii poly[maxN];
long double subs;

void dfs(int c, int p){
  visited[c] = true;
  curr_poly.pb(poly[c]);
  for(auto [i,x] : edge[c]){
    if(i == p) continue;
    pii target = {-poly[c].ff, x - poly[c].ss };
    if(visited[i]){
      pii orig = poly[i];
      if(orig != target){
        if(orig.ff == target.ff){
          printf("NO");
          exit(0);
        }else{
          long double nw = - ( 0.0 + orig.ss - target.ss) / ( 0.0 + orig.ff - target.ff);
          if( ccx > 1e17 ){
            ccx = nw;
          }else{
            if(fabsl(nw - ccx) > eps){
              printf("NO");
              exit(0);
            }
          }
        }
      }
    }else{
      poly[i] = target;
      dfs(i, c);
    }
  }
}

bool visited_val[maxN];

void dfs_val(int c, int p){
  visited_val[c] = true;

  val[c] = (subs * poly[c].ff + poly[c].ss);

  for(auto[i,x] : edge[c]){
    if(i == p) continue;
    if(visited_val[i]) continue;
    dfs_val(i, c);
  }
}

signed main(){
  
  int n,m;
  cin >> n >> m;

  F(m){
    int x,y,c;
    cin >> x >> y >> c;
    if(x > y) swap(x,y);
    if(!chk[mp(x,y)]){
      chk[mp(x,y)] = c;
    }else{
      if(chk[mp(x,y)] != c){
        printf("NO");
        exit(0);
      }
    }
    edge[x].pb(mp(y, c));
    edge[y].pb(mp(x, c));
  }

  Fl(i, 1, n+1){
    if(visited[i]) continue;
    poly[i] = {1, 0};
    curr_poly.clear();
    ccx = 1e18;
    dfs(i, 0);
    
    if(ccx > 1e17){
      long double l = -1e5;
      long double r = 1e5;
      Fi(xxxxx, 300){
        
        long double a = sub((2*l+r)/3);
        long double b = sub((2*r+l)/3);
        if(fabsl(a-b) < 1e-12){
          break;
        }else if(a > b){
          l = (2*l+r)/3;
        }else{
          r = (2*r+l)/3;
        }
      }
      subs = mid;
    }else{
      subs = ccx;
    }

    dfs_val(i, 0);
  }

  printf("YES\n");
  Fl(i, 1, n+1){
    printf("%.15Lf ", val[i]);
  }

  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 12 / 12
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 42 / 42