#include <bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")
#define PB push_back
#define sz(x) ((int)x.size())
#define i2 array<int,2>
using namespace std;
typedef long double ld;
const int oo = 2e9;
const int N = 100100;
const int cnst = 110;
const int con = 50;
queue<int> q;
bool was;
vector<i2> g[N];
int n, m, col[N], mrk[N], tt;
int cost = 0, nm[N];
void BAD(){
cout << "NO";
exit(0);
}
void dfs(int v, int vl){
if (was) return;
if (mrk[v] == tt){
if (col[v] != vl)
was = 1;
return;
}
mrk[v] = tt;
col[v] = vl;
cost += abs(vl);
for (i2 u : g[v])
dfs(u[0], u[1] - vl);
}
mt19937 rnd(chrono::system_clock().now().time_since_epoch().count());
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef _LOCAL
freopen("in.txt","r",stdin);
#endif // _LOCAL
cin >> n >> m;
for (int i = 0; i < m; i++){
int x, y, z; cin >> x >> y >> z;
x--; y--;
g[x].PB({y, z * 2});
g[y].PB({x, z * 2});
}
for (int i = 0; i < n; i++)
nm[i] = i;
fill(col, col + n, -oo);
// shuffle(nm, nm + n, rnd);
for (int ite = 0; ite < n; ite++){
// int i = nm[ite];
int i = ite;
if (col[i] != -oo) continue;
int best = oo, mem = -oo;
for (int vl = -cnst; vl <= con; vl++){
was = 0;
tt++;
cost = 0;
while (sz(q)) q.pop();
q.push(i);
col[i] = vl;
cost = abs(vl);
mrk[i] = tt;
while (!was && sz(q) && cost < best){
int v = q.front(); q.pop();
for (i2 u : g[v]){
if (mrk[u[0]] == tt){
if (col[u[0]] != u[1] - col[v]){
was = 1;
break;
}
} else {
q.push(u[0]);
mrk[u[0]] = tt;
col[u[0]] = u[1] - col[v];
cost += abs(col[u[0]]);
}
}
}
if (!was && best > cost){
best = cost;
mem = vl;
}
}
if (best == oo) BAD();
was = 0;
tt++;
dfs(i, mem);
}
cout << "YES\n";
for (int i = 0; i < n; i++)
cout << fixed << setprecision(10) << ld(col[i]) / 2.0 << " ";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2688 KB |
answer = YES |
2 |
Correct |
1 ms |
2688 KB |
answer = YES |
3 |
Correct |
1 ms |
2688 KB |
answer = YES |
4 |
Correct |
1 ms |
2688 KB |
answer = NO |
5 |
Correct |
1 ms |
2688 KB |
answer = YES |
6 |
Correct |
2 ms |
2688 KB |
answer = YES |
7 |
Correct |
2 ms |
2688 KB |
answer = YES |
8 |
Correct |
2 ms |
2688 KB |
answer = YES |
9 |
Correct |
2 ms |
2688 KB |
answer = NO |
10 |
Correct |
2 ms |
2688 KB |
answer = YES |
11 |
Correct |
2 ms |
2688 KB |
answer = YES |
12 |
Correct |
2 ms |
2688 KB |
answer = NO |
13 |
Correct |
1 ms |
2688 KB |
answer = YES |
14 |
Correct |
2 ms |
2688 KB |
answer = YES |
15 |
Correct |
2 ms |
2688 KB |
answer = YES |
16 |
Correct |
2 ms |
2688 KB |
answer = YES |
17 |
Correct |
2 ms |
2688 KB |
answer = YES |
18 |
Correct |
1 ms |
2688 KB |
answer = YES |
19 |
Correct |
2 ms |
2688 KB |
answer = YES |
20 |
Correct |
1 ms |
2688 KB |
answer = YES |
21 |
Correct |
2 ms |
2688 KB |
answer = YES |
22 |
Correct |
2 ms |
2688 KB |
answer = NO |
23 |
Correct |
2 ms |
2688 KB |
answer = NO |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2688 KB |
answer = YES |
2 |
Correct |
1 ms |
2688 KB |
answer = YES |
3 |
Correct |
1 ms |
2688 KB |
answer = YES |
4 |
Correct |
1 ms |
2688 KB |
answer = NO |
5 |
Correct |
1 ms |
2688 KB |
answer = YES |
6 |
Correct |
2 ms |
2688 KB |
answer = YES |
7 |
Correct |
2 ms |
2688 KB |
answer = YES |
8 |
Correct |
2 ms |
2688 KB |
answer = YES |
9 |
Correct |
2 ms |
2688 KB |
answer = NO |
10 |
Correct |
2 ms |
2688 KB |
answer = YES |
11 |
Correct |
2 ms |
2688 KB |
answer = YES |
12 |
Correct |
2 ms |
2688 KB |
answer = NO |
13 |
Correct |
1 ms |
2688 KB |
answer = YES |
14 |
Correct |
2 ms |
2688 KB |
answer = YES |
15 |
Correct |
2 ms |
2688 KB |
answer = YES |
16 |
Correct |
2 ms |
2688 KB |
answer = YES |
17 |
Correct |
2 ms |
2688 KB |
answer = YES |
18 |
Correct |
1 ms |
2688 KB |
answer = YES |
19 |
Correct |
2 ms |
2688 KB |
answer = YES |
20 |
Correct |
1 ms |
2688 KB |
answer = YES |
21 |
Correct |
2 ms |
2688 KB |
answer = YES |
22 |
Correct |
2 ms |
2688 KB |
answer = NO |
23 |
Correct |
2 ms |
2688 KB |
answer = NO |
24 |
Correct |
2 ms |
2688 KB |
answer = YES |
25 |
Correct |
2 ms |
2688 KB |
answer = YES |
26 |
Correct |
2 ms |
2688 KB |
answer = YES |
27 |
Correct |
2 ms |
2688 KB |
answer = YES |
28 |
Correct |
2 ms |
2688 KB |
answer = YES |
29 |
Correct |
2 ms |
2688 KB |
answer = YES |
30 |
Correct |
2 ms |
2688 KB |
answer = NO |
31 |
Correct |
2 ms |
2688 KB |
answer = YES |
32 |
Correct |
2 ms |
2688 KB |
answer = YES |
33 |
Correct |
2 ms |
2688 KB |
answer = YES |
34 |
Correct |
2 ms |
2688 KB |
answer = YES |
35 |
Correct |
2 ms |
2688 KB |
answer = YES |
36 |
Correct |
2 ms |
2688 KB |
answer = YES |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2688 KB |
answer = YES |
2 |
Correct |
1 ms |
2688 KB |
answer = YES |
3 |
Correct |
1 ms |
2688 KB |
answer = YES |
4 |
Correct |
1 ms |
2688 KB |
answer = NO |
5 |
Correct |
1 ms |
2688 KB |
answer = YES |
6 |
Correct |
2 ms |
2688 KB |
answer = YES |
7 |
Correct |
2 ms |
2688 KB |
answer = YES |
8 |
Correct |
2 ms |
2688 KB |
answer = YES |
9 |
Correct |
2 ms |
2688 KB |
answer = NO |
10 |
Correct |
2 ms |
2688 KB |
answer = YES |
11 |
Correct |
2 ms |
2688 KB |
answer = YES |
12 |
Correct |
2 ms |
2688 KB |
answer = NO |
13 |
Correct |
1 ms |
2688 KB |
answer = YES |
14 |
Correct |
2 ms |
2688 KB |
answer = YES |
15 |
Correct |
2 ms |
2688 KB |
answer = YES |
16 |
Correct |
2 ms |
2688 KB |
answer = YES |
17 |
Correct |
2 ms |
2688 KB |
answer = YES |
18 |
Correct |
1 ms |
2688 KB |
answer = YES |
19 |
Correct |
2 ms |
2688 KB |
answer = YES |
20 |
Correct |
1 ms |
2688 KB |
answer = YES |
21 |
Correct |
2 ms |
2688 KB |
answer = YES |
22 |
Correct |
2 ms |
2688 KB |
answer = NO |
23 |
Correct |
2 ms |
2688 KB |
answer = NO |
24 |
Correct |
2 ms |
2688 KB |
answer = YES |
25 |
Correct |
2 ms |
2688 KB |
answer = YES |
26 |
Correct |
2 ms |
2688 KB |
answer = YES |
27 |
Correct |
2 ms |
2688 KB |
answer = YES |
28 |
Correct |
2 ms |
2688 KB |
answer = YES |
29 |
Correct |
2 ms |
2688 KB |
answer = YES |
30 |
Correct |
2 ms |
2688 KB |
answer = NO |
31 |
Correct |
2 ms |
2688 KB |
answer = YES |
32 |
Correct |
2 ms |
2688 KB |
answer = YES |
33 |
Correct |
2 ms |
2688 KB |
answer = YES |
34 |
Correct |
2 ms |
2688 KB |
answer = YES |
35 |
Correct |
2 ms |
2688 KB |
answer = YES |
36 |
Correct |
2 ms |
2688 KB |
answer = YES |
37 |
Correct |
2 ms |
2688 KB |
answer = YES |
38 |
Correct |
2 ms |
2688 KB |
answer = YES |
39 |
Correct |
3 ms |
2688 KB |
answer = YES |
40 |
Correct |
3 ms |
2816 KB |
answer = YES |
41 |
Correct |
3 ms |
2688 KB |
answer = NO |
42 |
Correct |
7 ms |
2816 KB |
answer = YES |
43 |
Correct |
5 ms |
2816 KB |
answer = YES |
44 |
Correct |
5 ms |
2816 KB |
answer = YES |
45 |
Correct |
5 ms |
2816 KB |
answer = YES |
46 |
Correct |
4 ms |
2688 KB |
answer = YES |
47 |
Correct |
4 ms |
2816 KB |
answer = YES |
48 |
Correct |
4 ms |
2816 KB |
answer = YES |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2688 KB |
answer = YES |
2 |
Correct |
1 ms |
2688 KB |
answer = YES |
3 |
Correct |
1 ms |
2688 KB |
answer = YES |
4 |
Correct |
1 ms |
2688 KB |
answer = NO |
5 |
Correct |
1 ms |
2688 KB |
answer = YES |
6 |
Correct |
2 ms |
2688 KB |
answer = YES |
7 |
Correct |
2 ms |
2688 KB |
answer = YES |
8 |
Correct |
2 ms |
2688 KB |
answer = YES |
9 |
Correct |
2 ms |
2688 KB |
answer = NO |
10 |
Correct |
2 ms |
2688 KB |
answer = YES |
11 |
Correct |
2 ms |
2688 KB |
answer = YES |
12 |
Correct |
2 ms |
2688 KB |
answer = NO |
13 |
Correct |
1 ms |
2688 KB |
answer = YES |
14 |
Correct |
2 ms |
2688 KB |
answer = YES |
15 |
Correct |
2 ms |
2688 KB |
answer = YES |
16 |
Correct |
2 ms |
2688 KB |
answer = YES |
17 |
Correct |
2 ms |
2688 KB |
answer = YES |
18 |
Correct |
1 ms |
2688 KB |
answer = YES |
19 |
Correct |
2 ms |
2688 KB |
answer = YES |
20 |
Correct |
1 ms |
2688 KB |
answer = YES |
21 |
Correct |
2 ms |
2688 KB |
answer = YES |
22 |
Correct |
2 ms |
2688 KB |
answer = NO |
23 |
Correct |
2 ms |
2688 KB |
answer = NO |
24 |
Correct |
2 ms |
2688 KB |
answer = YES |
25 |
Correct |
2 ms |
2688 KB |
answer = YES |
26 |
Correct |
2 ms |
2688 KB |
answer = YES |
27 |
Correct |
2 ms |
2688 KB |
answer = YES |
28 |
Correct |
2 ms |
2688 KB |
answer = YES |
29 |
Correct |
2 ms |
2688 KB |
answer = YES |
30 |
Correct |
2 ms |
2688 KB |
answer = NO |
31 |
Correct |
2 ms |
2688 KB |
answer = YES |
32 |
Correct |
2 ms |
2688 KB |
answer = YES |
33 |
Correct |
2 ms |
2688 KB |
answer = YES |
34 |
Correct |
2 ms |
2688 KB |
answer = YES |
35 |
Correct |
2 ms |
2688 KB |
answer = YES |
36 |
Correct |
2 ms |
2688 KB |
answer = YES |
37 |
Correct |
2 ms |
2688 KB |
answer = YES |
38 |
Correct |
2 ms |
2688 KB |
answer = YES |
39 |
Correct |
3 ms |
2688 KB |
answer = YES |
40 |
Correct |
3 ms |
2816 KB |
answer = YES |
41 |
Correct |
3 ms |
2688 KB |
answer = NO |
42 |
Correct |
7 ms |
2816 KB |
answer = YES |
43 |
Correct |
5 ms |
2816 KB |
answer = YES |
44 |
Correct |
5 ms |
2816 KB |
answer = YES |
45 |
Correct |
5 ms |
2816 KB |
answer = YES |
46 |
Correct |
4 ms |
2688 KB |
answer = YES |
47 |
Correct |
4 ms |
2816 KB |
answer = YES |
48 |
Correct |
4 ms |
2816 KB |
answer = YES |
49 |
Correct |
45 ms |
3320 KB |
answer = YES |
50 |
Correct |
16 ms |
3456 KB |
answer = YES |
51 |
Correct |
45 ms |
3448 KB |
answer = YES |
52 |
Correct |
9 ms |
3072 KB |
answer = NO |
53 |
Correct |
5 ms |
2756 KB |
answer = YES |
54 |
Correct |
11 ms |
2816 KB |
answer = YES |
55 |
Correct |
20 ms |
3072 KB |
answer = YES |
56 |
Correct |
42 ms |
3320 KB |
answer = YES |
57 |
Correct |
35 ms |
3320 KB |
answer = YES |
58 |
Correct |
33 ms |
3320 KB |
answer = YES |
59 |
Correct |
23 ms |
3320 KB |
answer = YES |
60 |
Correct |
50 ms |
3448 KB |
answer = YES |
61 |
Correct |
18 ms |
3072 KB |
answer = YES |
62 |
Correct |
67 ms |
7416 KB |
answer = NO |
63 |
Correct |
70 ms |
7928 KB |
answer = YES |
64 |
Correct |
64 ms |
7416 KB |
answer = NO |
65 |
Correct |
68 ms |
7800 KB |
answer = YES |
66 |
Correct |
10 ms |
2816 KB |
answer = YES |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2688 KB |
answer = YES |
2 |
Correct |
1 ms |
2688 KB |
answer = YES |
3 |
Correct |
1 ms |
2688 KB |
answer = YES |
4 |
Correct |
1 ms |
2688 KB |
answer = NO |
5 |
Correct |
1 ms |
2688 KB |
answer = YES |
6 |
Correct |
2 ms |
2688 KB |
answer = YES |
7 |
Correct |
2 ms |
2688 KB |
answer = YES |
8 |
Correct |
2 ms |
2688 KB |
answer = YES |
9 |
Correct |
2 ms |
2688 KB |
answer = NO |
10 |
Correct |
2 ms |
2688 KB |
answer = YES |
11 |
Correct |
2 ms |
2688 KB |
answer = YES |
12 |
Correct |
2 ms |
2688 KB |
answer = NO |
13 |
Correct |
1 ms |
2688 KB |
answer = YES |
14 |
Correct |
2 ms |
2688 KB |
answer = YES |
15 |
Correct |
2 ms |
2688 KB |
answer = YES |
16 |
Correct |
2 ms |
2688 KB |
answer = YES |
17 |
Correct |
2 ms |
2688 KB |
answer = YES |
18 |
Correct |
1 ms |
2688 KB |
answer = YES |
19 |
Correct |
2 ms |
2688 KB |
answer = YES |
20 |
Correct |
1 ms |
2688 KB |
answer = YES |
21 |
Correct |
2 ms |
2688 KB |
answer = YES |
22 |
Correct |
2 ms |
2688 KB |
answer = NO |
23 |
Correct |
2 ms |
2688 KB |
answer = NO |
24 |
Correct |
2 ms |
2688 KB |
answer = YES |
25 |
Correct |
2 ms |
2688 KB |
answer = YES |
26 |
Correct |
2 ms |
2688 KB |
answer = YES |
27 |
Correct |
2 ms |
2688 KB |
answer = YES |
28 |
Correct |
2 ms |
2688 KB |
answer = YES |
29 |
Correct |
2 ms |
2688 KB |
answer = YES |
30 |
Correct |
2 ms |
2688 KB |
answer = NO |
31 |
Correct |
2 ms |
2688 KB |
answer = YES |
32 |
Correct |
2 ms |
2688 KB |
answer = YES |
33 |
Correct |
2 ms |
2688 KB |
answer = YES |
34 |
Correct |
2 ms |
2688 KB |
answer = YES |
35 |
Correct |
2 ms |
2688 KB |
answer = YES |
36 |
Correct |
2 ms |
2688 KB |
answer = YES |
37 |
Correct |
2 ms |
2688 KB |
answer = YES |
38 |
Correct |
2 ms |
2688 KB |
answer = YES |
39 |
Correct |
3 ms |
2688 KB |
answer = YES |
40 |
Correct |
3 ms |
2816 KB |
answer = YES |
41 |
Correct |
3 ms |
2688 KB |
answer = NO |
42 |
Correct |
7 ms |
2816 KB |
answer = YES |
43 |
Correct |
5 ms |
2816 KB |
answer = YES |
44 |
Correct |
5 ms |
2816 KB |
answer = YES |
45 |
Correct |
5 ms |
2816 KB |
answer = YES |
46 |
Correct |
4 ms |
2688 KB |
answer = YES |
47 |
Correct |
4 ms |
2816 KB |
answer = YES |
48 |
Correct |
4 ms |
2816 KB |
answer = YES |
49 |
Correct |
45 ms |
3320 KB |
answer = YES |
50 |
Correct |
16 ms |
3456 KB |
answer = YES |
51 |
Correct |
45 ms |
3448 KB |
answer = YES |
52 |
Correct |
9 ms |
3072 KB |
answer = NO |
53 |
Correct |
5 ms |
2756 KB |
answer = YES |
54 |
Correct |
11 ms |
2816 KB |
answer = YES |
55 |
Correct |
20 ms |
3072 KB |
answer = YES |
56 |
Correct |
42 ms |
3320 KB |
answer = YES |
57 |
Correct |
35 ms |
3320 KB |
answer = YES |
58 |
Correct |
33 ms |
3320 KB |
answer = YES |
59 |
Correct |
23 ms |
3320 KB |
answer = YES |
60 |
Correct |
50 ms |
3448 KB |
answer = YES |
61 |
Correct |
18 ms |
3072 KB |
answer = YES |
62 |
Correct |
67 ms |
7416 KB |
answer = NO |
63 |
Correct |
70 ms |
7928 KB |
answer = YES |
64 |
Correct |
64 ms |
7416 KB |
answer = NO |
65 |
Correct |
68 ms |
7800 KB |
answer = YES |
66 |
Correct |
10 ms |
2816 KB |
answer = YES |
67 |
Correct |
302 ms |
11656 KB |
answer = YES |
68 |
Correct |
283 ms |
11384 KB |
answer = YES |
69 |
Correct |
278 ms |
11384 KB |
answer = YES |
70 |
Correct |
143 ms |
14644 KB |
answer = YES |
71 |
Correct |
273 ms |
11512 KB |
answer = YES |
72 |
Execution timed out |
898 ms |
8952 KB |
Time limit exceeded |
73 |
Halted |
0 ms |
0 KB |
- |