oj.uz

Submission #518786

# Submission time Handle Problem Language Result Execution time Memory
518786 2022-01-24T15:50:26 Z Wayne_Yan Graph (BOI20_graph) C++17
100 / 100
 467 ms 37616 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB answer = YES
2 Correct 2 ms 2636 KB answer = YES
3 Correct 1 ms 2636 KB answer = YES
4 Correct 1 ms 2636 KB answer = NO
5 Correct 2 ms 2668 KB answer = YES
6 Correct 1 ms 2636 KB answer = YES
7 Correct 1 ms 2636 KB answer = YES
8 Correct 1 ms 2636 KB answer = YES
9 Correct 2 ms 2636 KB answer = NO
10 Correct 2 ms 2636 KB answer = YES
11 Correct 1 ms 2636 KB answer = YES
12 Correct 1 ms 2636 KB answer = NO
13 Correct 1 ms 2636 KB answer = YES
14 Correct 1 ms 2636 KB answer = YES
15 Correct 1 ms 2636 KB answer = YES
16 Correct 2 ms 2636 KB answer = YES
17 Correct 1 ms 2636 KB answer = YES
18 Correct 2 ms 2636 KB answer = YES
19 Correct 2 ms 2636 KB answer = YES
20 Correct 2 ms 2636 KB answer = YES
21 Correct 1 ms 2636 KB answer = YES
22 Correct 1 ms 2636 KB answer = NO
23 Correct 2 ms 2636 KB answer = NO

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB answer = YES
2 Correct 2 ms 2636 KB answer = YES
3 Correct 1 ms 2636 KB answer = YES
4 Correct 1 ms 2636 KB answer = NO
5 Correct 2 ms 2668 KB answer = YES
6 Correct 1 ms 2636 KB answer = YES
7 Correct 1 ms 2636 KB answer = YES
8 Correct 1 ms 2636 KB answer = YES
9 Correct 2 ms 2636 KB answer = NO
10 Correct 2 ms 2636 KB answer = YES
11 Correct 1 ms 2636 KB answer = YES
12 Correct 1 ms 2636 KB answer = NO
13 Correct 1 ms 2636 KB answer = YES
14 Correct 1 ms 2636 KB answer = YES
15 Correct 1 ms 2636 KB answer = YES
16 Correct 2 ms 2636 KB answer = YES
17 Correct 1 ms 2636 KB answer = YES
18 Correct 2 ms 2636 KB answer = YES
19 Correct 2 ms 2636 KB answer = YES
20 Correct 2 ms 2636 KB answer = YES
21 Correct 1 ms 2636 KB answer = YES
22 Correct 1 ms 2636 KB answer = NO
23 Correct 2 ms 2636 KB answer = NO
24 Correct 2 ms 2636 KB answer = YES
25 Correct 1 ms 2636 KB answer = YES
26 Correct 2 ms 2636 KB answer = YES
27 Correct 2 ms 2636 KB answer = YES
28 Correct 2 ms 2636 KB answer = YES
29 Correct 2 ms 2636 KB answer = YES
30 Correct 2 ms 2636 KB answer = NO
31 Correct 2 ms 2636 KB answer = YES
32 Correct 2 ms 2636 KB answer = YES
33 Correct 2 ms 2636 KB answer = YES
34 Correct 2 ms 2636 KB answer = YES
35 Correct 2 ms 2636 KB answer = YES
36 Correct 2 ms 2636 KB answer = YES

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB answer = YES
2 Correct 2 ms 2636 KB answer = YES
3 Correct 1 ms 2636 KB answer = YES
4 Correct 1 ms 2636 KB answer = NO
5 Correct 2 ms 2668 KB answer = YES
6 Correct 1 ms 2636 KB answer = YES
7 Correct 1 ms 2636 KB answer = YES
8 Correct 1 ms 2636 KB answer = YES
9 Correct 2 ms 2636 KB answer = NO
10 Correct 2 ms 2636 KB answer = YES
11 Correct 1 ms 2636 KB answer = YES
12 Correct 1 ms 2636 KB answer = NO
13 Correct 1 ms 2636 KB answer = YES
14 Correct 1 ms 2636 KB answer = YES
15 Correct 1 ms 2636 KB answer = YES
16 Correct 2 ms 2636 KB answer = YES
17 Correct 1 ms 2636 KB answer = YES
18 Correct 2 ms 2636 KB answer = YES
19 Correct 2 ms 2636 KB answer = YES
20 Correct 2 ms 2636 KB answer = YES
21 Correct 1 ms 2636 KB answer = YES
22 Correct 1 ms 2636 KB answer = NO
23 Correct 2 ms 2636 KB answer = NO
24 Correct 2 ms 2636 KB answer = YES
25 Correct 1 ms 2636 KB answer = YES
26 Correct 2 ms 2636 KB answer = YES
27 Correct 2 ms 2636 KB answer = YES
28 Correct 2 ms 2636 KB answer = YES
29 Correct 2 ms 2636 KB answer = YES
30 Correct 2 ms 2636 KB answer = NO
31 Correct 2 ms 2636 KB answer = YES
32 Correct 2 ms 2636 KB answer = YES
33 Correct 2 ms 2636 KB answer = YES
34 Correct 2 ms 2636 KB answer = YES
35 Correct 2 ms 2636 KB answer = YES
36 Correct 2 ms 2636 KB answer = YES
37 Correct 2 ms 2636 KB answer = YES
38 Correct 3 ms 2640 KB answer = YES
39 Correct 3 ms 2636 KB answer = YES
40 Correct 3 ms 2764 KB answer = YES
41 Correct 2 ms 2684 KB answer = NO
42 Correct 4 ms 2732 KB answer = YES
43 Correct 5 ms 2760 KB answer = YES
44 Correct 4 ms 2764 KB answer = YES
45 Correct 3 ms 2764 KB answer = YES
46 Correct 3 ms 2636 KB answer = YES
47 Correct 3 ms 2764 KB answer = YES
48 Correct 3 ms 2764 KB answer = YES

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB answer = YES
2 Correct 2 ms 2636 KB answer = YES
3 Correct 1 ms 2636 KB answer = YES
4 Correct 1 ms 2636 KB answer = NO
5 Correct 2 ms 2668 KB answer = YES
6 Correct 1 ms 2636 KB answer = YES
7 Correct 1 ms 2636 KB answer = YES
8 Correct 1 ms 2636 KB answer = YES
9 Correct 2 ms 2636 KB answer = NO
10 Correct 2 ms 2636 KB answer = YES
11 Correct 1 ms 2636 KB answer = YES
12 Correct 1 ms 2636 KB answer = NO
13 Correct 1 ms 2636 KB answer = YES
14 Correct 1 ms 2636 KB answer = YES
15 Correct 1 ms 2636 KB answer = YES
16 Correct 2 ms 2636 KB answer = YES
17 Correct 1 ms 2636 KB answer = YES
18 Correct 2 ms 2636 KB answer = YES
19 Correct 2 ms 2636 KB answer = YES
20 Correct 2 ms 2636 KB answer = YES
21 Correct 1 ms 2636 KB answer = YES
22 Correct 1 ms 2636 KB answer = NO
23 Correct 2 ms 2636 KB answer = NO
24 Correct 2 ms 2636 KB answer = YES
25 Correct 1 ms 2636 KB answer = YES
26 Correct 2 ms 2636 KB answer = YES
27 Correct 2 ms 2636 KB answer = YES
28 Correct 2 ms 2636 KB answer = YES
29 Correct 2 ms 2636 KB answer = YES
30 Correct 2 ms 2636 KB answer = NO
31 Correct 2 ms 2636 KB answer = YES
32 Correct 2 ms 2636 KB answer = YES
33 Correct 2 ms 2636 KB answer = YES
34 Correct 2 ms 2636 KB answer = YES
35 Correct 2 ms 2636 KB answer = YES
36 Correct 2 ms 2636 KB answer = YES
37 Correct 2 ms 2636 KB answer = YES
38 Correct 3 ms 2640 KB answer = YES
39 Correct 3 ms 2636 KB answer = YES
40 Correct 3 ms 2764 KB answer = YES
41 Correct 2 ms 2684 KB answer = NO
42 Correct 4 ms 2732 KB answer = YES
43 Correct 5 ms 2760 KB answer = YES
44 Correct 4 ms 2764 KB answer = YES
45 Correct 3 ms 2764 KB answer = YES
46 Correct 3 ms 2636 KB answer = YES
47 Correct 3 ms 2764 KB answer = YES
48 Correct 3 ms 2764 KB answer = YES
49 Correct 37 ms 4216 KB answer = YES
50 Correct 17 ms 4684 KB answer = YES
51 Correct 20 ms 4684 KB answer = YES
52 Correct 13 ms 3724 KB answer = NO
53 Correct 3 ms 2764 KB answer = YES
54 Correct 7 ms 3020 KB answer = YES
55 Correct 16 ms 3532 KB answer = YES
56 Correct 38 ms 4164 KB answer = YES
57 Correct 33 ms 4016 KB answer = YES
58 Correct 27 ms 3996 KB answer = YES
59 Correct 15 ms 3972 KB answer = YES
60 Correct 29 ms 4304 KB answer = YES
61 Correct 9 ms 3404 KB answer = YES
62 Correct 15 ms 3788 KB answer = NO
63 Correct 340 ms 20728 KB answer = YES
64 Correct 367 ms 20540 KB answer = NO
65 Correct 298 ms 20776 KB answer = YES
66 Correct 5 ms 2892 KB answer = YES

Subtask #5
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB answer = YES
2 Correct 2 ms 2636 KB answer = YES
3 Correct 1 ms 2636 KB answer = YES
4 Correct 1 ms 2636 KB answer = NO
5 Correct 2 ms 2668 KB answer = YES
6 Correct 1 ms 2636 KB answer = YES
7 Correct 1 ms 2636 KB answer = YES
8 Correct 1 ms 2636 KB answer = YES
9 Correct 2 ms 2636 KB answer = NO
10 Correct 2 ms 2636 KB answer = YES
11 Correct 1 ms 2636 KB answer = YES
12 Correct 1 ms 2636 KB answer = NO
13 Correct 1 ms 2636 KB answer = YES
14 Correct 1 ms 2636 KB answer = YES
15 Correct 1 ms 2636 KB answer = YES
16 Correct 2 ms 2636 KB answer = YES
17 Correct 1 ms 2636 KB answer = YES
18 Correct 2 ms 2636 KB answer = YES
19 Correct 2 ms 2636 KB answer = YES
20 Correct 2 ms 2636 KB answer = YES
21 Correct 1 ms 2636 KB answer = YES
22 Correct 1 ms 2636 KB answer = NO
23 Correct 2 ms 2636 KB answer = NO
24 Correct 2 ms 2636 KB answer = YES
25 Correct 1 ms 2636 KB answer = YES
26 Correct 2 ms 2636 KB answer = YES
27 Correct 2 ms 2636 KB answer = YES
28 Correct 2 ms 2636 KB answer = YES
29 Correct 2 ms 2636 KB answer = YES
30 Correct 2 ms 2636 KB answer = NO
31 Correct 2 ms 2636 KB answer = YES
32 Correct 2 ms 2636 KB answer = YES
33 Correct 2 ms 2636 KB answer = YES
34 Correct 2 ms 2636 KB answer = YES
35 Correct 2 ms 2636 KB answer = YES
36 Correct 2 ms 2636 KB answer = YES
37 Correct 2 ms 2636 KB answer = YES
38 Correct 3 ms 2640 KB answer = YES
39 Correct 3 ms 2636 KB answer = YES
40 Correct 3 ms 2764 KB answer = YES
41 Correct 2 ms 2684 KB answer = NO
42 Correct 4 ms 2732 KB answer = YES
43 Correct 5 ms 2760 KB answer = YES
44 Correct 4 ms 2764 KB answer = YES
45 Correct 3 ms 2764 KB answer = YES
46 Correct 3 ms 2636 KB answer = YES
47 Correct 3 ms 2764 KB answer = YES
48 Correct 3 ms 2764 KB answer = YES
49 Correct 37 ms 4216 KB answer = YES
50 Correct 17 ms 4684 KB answer = YES
51 Correct 20 ms 4684 KB answer = YES
52 Correct 13 ms 3724 KB answer = NO
53 Correct 3 ms 2764 KB answer = YES
54 Correct 7 ms 3020 KB answer = YES
55 Correct 16 ms 3532 KB answer = YES
56 Correct 38 ms 4164 KB answer = YES
57 Correct 33 ms 4016 KB answer = YES
58 Correct 27 ms 3996 KB answer = YES
59 Correct 15 ms 3972 KB answer = YES
60 Correct 29 ms 4304 KB answer = YES
61 Correct 9 ms 3404 KB answer = YES
62 Correct 15 ms 3788 KB answer = NO
63 Correct 340 ms 20728 KB answer = YES
64 Correct 367 ms 20540 KB answer = NO
65 Correct 298 ms 20776 KB answer = YES
66 Correct 5 ms 2892 KB answer = YES
67 Correct 239 ms 25304 KB answer = YES
68 Correct 157 ms 25172 KB answer = YES
69 Correct 181 ms 25128 KB answer = YES
70 Correct 264 ms 37616 KB answer = YES
71 Correct 160 ms 25192 KB answer = YES
72 Correct 401 ms 18016 KB answer = YES
73 Correct 211 ms 17920 KB answer = YES
74 Correct 122 ms 16320 KB answer = YES
75 Correct 87 ms 11632 KB answer = NO
76 Correct 40 ms 4596 KB answer = YES
77 Correct 80 ms 6468 KB answer = YES
78 Correct 158 ms 9164 KB answer = YES
79 Correct 362 ms 15800 KB answer = YES
80 Correct 182 ms 16316 KB answer = YES
81 Correct 158 ms 19268 KB answer = NO
82 Correct 213 ms 25808 KB answer = YES
83 Correct 246 ms 26644 KB answer = YES
84 Correct 285 ms 26576 KB answer = YES
85 Correct 192 ms 26476 KB answer = YES
86 Correct 164 ms 26576 KB answer = YES
87 Correct 167 ms 18476 KB answer = NO
88 Correct 247 ms 21556 KB answer = YES
89 Correct 241 ms 17720 KB answer = YES
90 Correct 189 ms 17616 KB answer = YES
91 Correct 196 ms 17728 KB answer = YES
92 Correct 91 ms 10972 KB answer = YES
93 Correct 98 ms 10980 KB answer = YES
94 Correct 151 ms 22972 KB answer = NO
95 Correct 137 ms 15940 KB answer = NO
96 Correct 467 ms 34008 KB answer = YES
97 Correct 116 ms 22972 KB answer = NO