#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-12);
if(fabsl(a-b) < 1e-13){
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;
}
# |
결과 |
실행 시간 |
메모리 |
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 |
2 ms |
2636 KB |
answer = NO |
5 |
Correct |
1 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 |
2 ms |
2636 KB |
answer = NO |
10 |
Correct |
1 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 |
2 ms |
2636 KB |
answer = YES |
15 |
Correct |
2 ms |
2636 KB |
answer = YES |
16 |
Correct |
1 ms |
2636 KB |
answer = YES |
17 |
Correct |
2 ms |
2636 KB |
answer = YES |
18 |
Correct |
1 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 |
2 ms |
2636 KB |
answer = NO |
# |
결과 |
실행 시간 |
메모리 |
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 |
2 ms |
2636 KB |
answer = NO |
5 |
Correct |
1 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 |
2 ms |
2636 KB |
answer = NO |
10 |
Correct |
1 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 |
2 ms |
2636 KB |
answer = YES |
15 |
Correct |
2 ms |
2636 KB |
answer = YES |
16 |
Correct |
1 ms |
2636 KB |
answer = YES |
17 |
Correct |
2 ms |
2636 KB |
answer = YES |
18 |
Correct |
1 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 |
2 ms |
2636 KB |
answer = NO |
24 |
Correct |
2 ms |
2636 KB |
answer = YES |
25 |
Correct |
2 ms |
2636 KB |
answer = YES |
26 |
Correct |
2 ms |
2636 KB |
answer = YES |
27 |
Correct |
1 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 |
1 ms |
2636 KB |
answer = YES |
35 |
Correct |
2 ms |
2636 KB |
answer = YES |
36 |
Correct |
1 ms |
2636 KB |
answer = YES |
# |
결과 |
실행 시간 |
메모리 |
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 |
2 ms |
2636 KB |
answer = NO |
5 |
Correct |
1 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 |
2 ms |
2636 KB |
answer = NO |
10 |
Correct |
1 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 |
2 ms |
2636 KB |
answer = YES |
15 |
Correct |
2 ms |
2636 KB |
answer = YES |
16 |
Correct |
1 ms |
2636 KB |
answer = YES |
17 |
Correct |
2 ms |
2636 KB |
answer = YES |
18 |
Correct |
1 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 |
2 ms |
2636 KB |
answer = NO |
24 |
Correct |
2 ms |
2636 KB |
answer = YES |
25 |
Correct |
2 ms |
2636 KB |
answer = YES |
26 |
Correct |
2 ms |
2636 KB |
answer = YES |
27 |
Correct |
1 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 |
1 ms |
2636 KB |
answer = YES |
35 |
Correct |
2 ms |
2636 KB |
answer = YES |
36 |
Correct |
1 ms |
2636 KB |
answer = YES |
37 |
Correct |
2 ms |
2636 KB |
answer = YES |
38 |
Correct |
2 ms |
2636 KB |
answer = YES |
39 |
Correct |
2 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 |
2764 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 |
4 ms |
2636 KB |
answer = YES |
47 |
Correct |
4 ms |
2764 KB |
answer = YES |
48 |
Correct |
3 ms |
2764 KB |
answer = YES |
# |
결과 |
실행 시간 |
메모리 |
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 |
2 ms |
2636 KB |
answer = NO |
5 |
Correct |
1 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 |
2 ms |
2636 KB |
answer = NO |
10 |
Correct |
1 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 |
2 ms |
2636 KB |
answer = YES |
15 |
Correct |
2 ms |
2636 KB |
answer = YES |
16 |
Correct |
1 ms |
2636 KB |
answer = YES |
17 |
Correct |
2 ms |
2636 KB |
answer = YES |
18 |
Correct |
1 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 |
2 ms |
2636 KB |
answer = NO |
24 |
Correct |
2 ms |
2636 KB |
answer = YES |
25 |
Correct |
2 ms |
2636 KB |
answer = YES |
26 |
Correct |
2 ms |
2636 KB |
answer = YES |
27 |
Correct |
1 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 |
1 ms |
2636 KB |
answer = YES |
35 |
Correct |
2 ms |
2636 KB |
answer = YES |
36 |
Correct |
1 ms |
2636 KB |
answer = YES |
37 |
Correct |
2 ms |
2636 KB |
answer = YES |
38 |
Correct |
2 ms |
2636 KB |
answer = YES |
39 |
Correct |
2 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 |
2764 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 |
4 ms |
2636 KB |
answer = YES |
47 |
Correct |
4 ms |
2764 KB |
answer = YES |
48 |
Correct |
3 ms |
2764 KB |
answer = YES |
49 |
Correct |
23 ms |
4300 KB |
answer = YES |
50 |
Correct |
17 ms |
4676 KB |
answer = YES |
51 |
Correct |
24 ms |
4676 KB |
answer = YES |
52 |
Correct |
15 ms |
3772 KB |
answer = NO |
53 |
Correct |
3 ms |
2764 KB |
answer = YES |
54 |
Correct |
5 ms |
3020 KB |
answer = YES |
55 |
Correct |
10 ms |
3404 KB |
answer = YES |
56 |
Correct |
19 ms |
4164 KB |
answer = YES |
57 |
Correct |
18 ms |
4096 KB |
answer = YES |
58 |
Correct |
18 ms |
4148 KB |
answer = YES |
59 |
Correct |
14 ms |
4088 KB |
answer = YES |
60 |
Correct |
18 ms |
4296 KB |
answer = YES |
61 |
Correct |
9 ms |
3536 KB |
answer = YES |
62 |
Correct |
18 ms |
4112 KB |
answer = NO |
63 |
Correct |
315 ms |
23068 KB |
answer = YES |
64 |
Correct |
332 ms |
22728 KB |
answer = NO |
65 |
Correct |
324 ms |
23120 KB |
answer = YES |
66 |
Correct |
5 ms |
2896 KB |
answer = YES |
# |
결과 |
실행 시간 |
메모리 |
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 |
2 ms |
2636 KB |
answer = NO |
5 |
Correct |
1 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 |
2 ms |
2636 KB |
answer = NO |
10 |
Correct |
1 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 |
2 ms |
2636 KB |
answer = YES |
15 |
Correct |
2 ms |
2636 KB |
answer = YES |
16 |
Correct |
1 ms |
2636 KB |
answer = YES |
17 |
Correct |
2 ms |
2636 KB |
answer = YES |
18 |
Correct |
1 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 |
2 ms |
2636 KB |
answer = NO |
24 |
Correct |
2 ms |
2636 KB |
answer = YES |
25 |
Correct |
2 ms |
2636 KB |
answer = YES |
26 |
Correct |
2 ms |
2636 KB |
answer = YES |
27 |
Correct |
1 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 |
1 ms |
2636 KB |
answer = YES |
35 |
Correct |
2 ms |
2636 KB |
answer = YES |
36 |
Correct |
1 ms |
2636 KB |
answer = YES |
37 |
Correct |
2 ms |
2636 KB |
answer = YES |
38 |
Correct |
2 ms |
2636 KB |
answer = YES |
39 |
Correct |
2 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 |
2764 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 |
4 ms |
2636 KB |
answer = YES |
47 |
Correct |
4 ms |
2764 KB |
answer = YES |
48 |
Correct |
3 ms |
2764 KB |
answer = YES |
49 |
Correct |
23 ms |
4300 KB |
answer = YES |
50 |
Correct |
17 ms |
4676 KB |
answer = YES |
51 |
Correct |
24 ms |
4676 KB |
answer = YES |
52 |
Correct |
15 ms |
3772 KB |
answer = NO |
53 |
Correct |
3 ms |
2764 KB |
answer = YES |
54 |
Correct |
5 ms |
3020 KB |
answer = YES |
55 |
Correct |
10 ms |
3404 KB |
answer = YES |
56 |
Correct |
19 ms |
4164 KB |
answer = YES |
57 |
Correct |
18 ms |
4096 KB |
answer = YES |
58 |
Correct |
18 ms |
4148 KB |
answer = YES |
59 |
Correct |
14 ms |
4088 KB |
answer = YES |
60 |
Correct |
18 ms |
4296 KB |
answer = YES |
61 |
Correct |
9 ms |
3536 KB |
answer = YES |
62 |
Correct |
18 ms |
4112 KB |
answer = NO |
63 |
Correct |
315 ms |
23068 KB |
answer = YES |
64 |
Correct |
332 ms |
22728 KB |
answer = NO |
65 |
Correct |
324 ms |
23120 KB |
answer = YES |
66 |
Correct |
5 ms |
2896 KB |
answer = YES |
67 |
Correct |
223 ms |
26484 KB |
answer = YES |
68 |
Correct |
150 ms |
26428 KB |
answer = YES |
69 |
Correct |
142 ms |
26428 KB |
answer = YES |
70 |
Correct |
269 ms |
40300 KB |
answer = YES |
71 |
Correct |
153 ms |
26480 KB |
answer = YES |
72 |
Correct |
278 ms |
19260 KB |
answer = YES |
73 |
Correct |
218 ms |
19196 KB |
answer = YES |
74 |
Correct |
126 ms |
17252 KB |
answer = YES |
75 |
Correct |
99 ms |
12516 KB |
answer = NO |
76 |
Correct |
22 ms |
4688 KB |
answer = YES |
77 |
Correct |
59 ms |
6776 KB |
answer = YES |
78 |
Correct |
107 ms |
9836 KB |
answer = YES |
79 |
Correct |
231 ms |
16856 KB |
answer = YES |
80 |
Incorrect |
204 ms |
17212 KB |
participant answer is larger than the answer of jury |
81 |
Halted |
0 ms |
0 KB |
- |