oj.uz

Submission #518781

# Submission time Handle Problem Language Result Execution time Memory
518781 2022-01-24T15:32:09 Z Wayne_Yan Graph (BOI20_graph) C++17
58 / 100
 366 ms 25252 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;
  for(pii p : curr_poly){
    ans += fabsl(f(p, x));
  }
  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, 200){
        
        long double a = sub(mid);
        long double b = sub(mid + 1e-14);
        if(fabsl(a-b) < 1e-15){
          break;
        }else if(a > b){
          l = mid;
        }else{
          r = mid;
        }
      }
      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 2 ms 2636 KB answer = YES
2 Correct 1 ms 2636 KB answer = YES
3 Correct 1 ms 2636 KB answer = YES
4 Correct 2 ms 2636 KB answer = NO
5 Correct 2 ms 2636 KB answer = YES
6 Correct 2 ms 2636 KB answer = YES
7 Correct 2 ms 2636 KB answer = YES
8 Correct 2 ms 2636 KB answer = YES
9 Correct 1 ms 2636 KB answer = NO
10 Correct 1 ms 2636 KB answer = YES
11 Correct 2 ms 2636 KB answer = YES
12 Correct 1 ms 2636 KB answer = NO
13 Correct 2 ms 2636 KB answer = YES
14 Correct 2 ms 2636 KB answer = YES
15 Correct 2 ms 2636 KB answer = YES
16 Correct 2 ms 2636 KB answer = YES
17 Correct 2 ms 2636 KB answer = YES
18 Correct 2 ms 2636 KB answer = YES
19 Correct 1 ms 2636 KB answer = YES
20 Correct 1 ms 2636 KB answer = YES
21 Correct 2 ms 2636 KB answer = YES
22 Correct 1 ms 2636 KB answer = NO
23 Correct 1 ms 2636 KB answer = NO

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB answer = YES
2 Correct 1 ms 2636 KB answer = YES
3 Correct 1 ms 2636 KB answer = YES
4 Correct 2 ms 2636 KB answer = NO
5 Correct 2 ms 2636 KB answer = YES
6 Correct 2 ms 2636 KB answer = YES
7 Correct 2 ms 2636 KB answer = YES
8 Correct 2 ms 2636 KB answer = YES
9 Correct 1 ms 2636 KB answer = NO
10 Correct 1 ms 2636 KB answer = YES
11 Correct 2 ms 2636 KB answer = YES
12 Correct 1 ms 2636 KB answer = NO
13 Correct 2 ms 2636 KB answer = YES
14 Correct 2 ms 2636 KB answer = YES
15 Correct 2 ms 2636 KB answer = YES
16 Correct 2 ms 2636 KB answer = YES
17 Correct 2 ms 2636 KB answer = YES
18 Correct 2 ms 2636 KB answer = YES
19 Correct 1 ms 2636 KB answer = YES
20 Correct 1 ms 2636 KB answer = YES
21 Correct 2 ms 2636 KB answer = YES
22 Correct 1 ms 2636 KB answer = NO
23 Correct 1 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 3 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 1 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 2 ms 2636 KB answer = YES
2 Correct 1 ms 2636 KB answer = YES
3 Correct 1 ms 2636 KB answer = YES
4 Correct 2 ms 2636 KB answer = NO
5 Correct 2 ms 2636 KB answer = YES
6 Correct 2 ms 2636 KB answer = YES
7 Correct 2 ms 2636 KB answer = YES
8 Correct 2 ms 2636 KB answer = YES
9 Correct 1 ms 2636 KB answer = NO
10 Correct 1 ms 2636 KB answer = YES
11 Correct 2 ms 2636 KB answer = YES
12 Correct 1 ms 2636 KB answer = NO
13 Correct 2 ms 2636 KB answer = YES
14 Correct 2 ms 2636 KB answer = YES
15 Correct 2 ms 2636 KB answer = YES
16 Correct 2 ms 2636 KB answer = YES
17 Correct 2 ms 2636 KB answer = YES
18 Correct 2 ms 2636 KB answer = YES
19 Correct 1 ms 2636 KB answer = YES
20 Correct 1 ms 2636 KB answer = YES
21 Correct 2 ms 2636 KB answer = YES
22 Correct 1 ms 2636 KB answer = NO
23 Correct 1 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 3 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 1 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 3 ms 2636 KB answer = YES
38 Correct 2 ms 2636 KB answer = YES
39 Correct 3 ms 2636 KB answer = YES
40 Correct 3 ms 2764 KB answer = YES
41 Correct 2 ms 2764 KB answer = NO
42 Correct 3 ms 2716 KB answer = YES
43 Correct 3 ms 2764 KB answer = YES
44 Correct 3 ms 2764 KB answer = YES
45 Correct 3 ms 2764 KB answer = YES
46 Correct 2 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 2 ms 2636 KB answer = YES
2 Correct 1 ms 2636 KB answer = YES
3 Correct 1 ms 2636 KB answer = YES
4 Correct 2 ms 2636 KB answer = NO
5 Correct 2 ms 2636 KB answer = YES
6 Correct 2 ms 2636 KB answer = YES
7 Correct 2 ms 2636 KB answer = YES
8 Correct 2 ms 2636 KB answer = YES
9 Correct 1 ms 2636 KB answer = NO
10 Correct 1 ms 2636 KB answer = YES
11 Correct 2 ms 2636 KB answer = YES
12 Correct 1 ms 2636 KB answer = NO
13 Correct 2 ms 2636 KB answer = YES
14 Correct 2 ms 2636 KB answer = YES
15 Correct 2 ms 2636 KB answer = YES
16 Correct 2 ms 2636 KB answer = YES
17 Correct 2 ms 2636 KB answer = YES
18 Correct 2 ms 2636 KB answer = YES
19 Correct 1 ms 2636 KB answer = YES
20 Correct 1 ms 2636 KB answer = YES
21 Correct 2 ms 2636 KB answer = YES
22 Correct 1 ms 2636 KB answer = NO
23 Correct 1 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 3 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 1 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 3 ms 2636 KB answer = YES
38 Correct 2 ms 2636 KB answer = YES
39 Correct 3 ms 2636 KB answer = YES
40 Correct 3 ms 2764 KB answer = YES
41 Correct 2 ms 2764 KB answer = NO
42 Correct 3 ms 2716 KB answer = YES
43 Correct 3 ms 2764 KB answer = YES
44 Correct 3 ms 2764 KB answer = YES
45 Correct 3 ms 2764 KB answer = YES
46 Correct 2 ms 2636 KB answer = YES
47 Correct 3 ms 2764 KB answer = YES
48 Correct 3 ms 2764 KB answer = YES
49 Correct 32 ms 4300 KB answer = YES
50 Correct 21 ms 4684 KB answer = YES
51 Correct 25 ms 4600 KB answer = YES
52 Correct 12 ms 3660 KB answer = NO
53 Correct 3 ms 2816 KB answer = YES
54 Correct 6 ms 3020 KB answer = YES
55 Correct 13 ms 3460 KB answer = YES
56 Correct 22 ms 4200 KB answer = YES
57 Correct 19 ms 4036 KB answer = YES
58 Correct 25 ms 4028 KB answer = YES
59 Correct 15 ms 4072 KB answer = YES
60 Correct 20 ms 4152 KB answer = YES
61 Correct 9 ms 3404 KB answer = YES
62 Correct 15 ms 3788 KB answer = NO
63 Correct 319 ms 20756 KB answer = YES
64 Correct 366 ms 20472 KB answer = NO
65 Correct 321 ms 20796 KB answer = YES
66 Correct 8 ms 2892 KB answer = YES

Subtask #5
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB answer = YES
2 Correct 1 ms 2636 KB answer = YES
3 Correct 1 ms 2636 KB answer = YES
4 Correct 2 ms 2636 KB answer = NO
5 Correct 2 ms 2636 KB answer = YES
6 Correct 2 ms 2636 KB answer = YES
7 Correct 2 ms 2636 KB answer = YES
8 Correct 2 ms 2636 KB answer = YES
9 Correct 1 ms 2636 KB answer = NO
10 Correct 1 ms 2636 KB answer = YES
11 Correct 2 ms 2636 KB answer = YES
12 Correct 1 ms 2636 KB answer = NO
13 Correct 2 ms 2636 KB answer = YES
14 Correct 2 ms 2636 KB answer = YES
15 Correct 2 ms 2636 KB answer = YES
16 Correct 2 ms 2636 KB answer = YES
17 Correct 2 ms 2636 KB answer = YES
18 Correct 2 ms 2636 KB answer = YES
19 Correct 1 ms 2636 KB answer = YES
20 Correct 1 ms 2636 KB answer = YES
21 Correct 2 ms 2636 KB answer = YES
22 Correct 1 ms 2636 KB answer = NO
23 Correct 1 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 3 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 1 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 3 ms 2636 KB answer = YES
38 Correct 2 ms 2636 KB answer = YES
39 Correct 3 ms 2636 KB answer = YES
40 Correct 3 ms 2764 KB answer = YES
41 Correct 2 ms 2764 KB answer = NO
42 Correct 3 ms 2716 KB answer = YES
43 Correct 3 ms 2764 KB answer = YES
44 Correct 3 ms 2764 KB answer = YES
45 Correct 3 ms 2764 KB answer = YES
46 Correct 2 ms 2636 KB answer = YES
47 Correct 3 ms 2764 KB answer = YES
48 Correct 3 ms 2764 KB answer = YES
49 Correct 32 ms 4300 KB answer = YES
50 Correct 21 ms 4684 KB answer = YES
51 Correct 25 ms 4600 KB answer = YES
52 Correct 12 ms 3660 KB answer = NO
53 Correct 3 ms 2816 KB answer = YES
54 Correct 6 ms 3020 KB answer = YES
55 Correct 13 ms 3460 KB answer = YES
56 Correct 22 ms 4200 KB answer = YES
57 Correct 19 ms 4036 KB answer = YES
58 Correct 25 ms 4028 KB answer = YES
59 Correct 15 ms 4072 KB answer = YES
60 Correct 20 ms 4152 KB answer = YES
61 Correct 9 ms 3404 KB answer = YES
62 Correct 15 ms 3788 KB answer = NO
63 Correct 319 ms 20756 KB answer = YES
64 Correct 366 ms 20472 KB answer = NO
65 Correct 321 ms 20796 KB answer = YES
66 Correct 8 ms 2892 KB answer = YES
67 Incorrect 234 ms 25252 KB participant answer is larger than the answer of jury
68 Halted 0 ms 0 KB -