#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
#define pb push_back
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define lb lower_bound
#define ub upper_bound
#define sz(v) int((v).size())
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
void solve() {
int n, m;
cin >> n >> m;
vector <vector <pair <int, int>>> graph(n+1);
vector <pair <pii, int>> edges;
for (int i = 1; i <= m; i++) {
int a, b;
int c;
cin >> a >> b >> c;
c *= 10;
edges.pb(mp(mp(a, b), c));
graph[a].pb(mp(b, c));
graph[b].pb(mp(a, c));
}
const int range = 291;
vector <vector <bool>> can(n+1, vector <bool> (range, 1));
vector <vector <int>> value(n+1, vector <int> (range)), sum(n+1, vector <int> (range));
vector <pii> acc(n+1, mp(2e9, 0));
vector <int> link(n+1), saizu(n+1, 1);
iota(all(link), 0);
function <int(int)> find = [&](int n) {
if (link[n] == n) return n;
return link[n] = find(link[n]);
};
function <void(int, int)> unite = [&](int a, int b) {
a = find(a); b = find(b);
if (a == b) return;
if (saizu[a] < saizu[b]) swap(a, b);
saizu[a] += saizu[b];
link[b] = a;
};
for (auto to : edges) {
auto a = to.first.first, b = to.first.second;
unite(a, b);
}
vector <int> used(n+1);
function <void(int, int, int)> dfs = [&](int v, int val, int i) {
value[v][i] = val;
used[v] = 1;
for (auto to : graph[v]) {
if (used[to.first]) continue;
dfs(to.first, to.second-val, i);
}
};
set <int> reps;
for (int i = 1; i <= n; i++) reps.insert(find(i));
for (int j = 0; j < range; j++) {
for (int i = 1; i <= n; i++) {
if (i == find(i)) {
dfs(i, (j-range/2), j);
}
}
for (int i = 1; i <= n; i++) {
sum[find(i)][j] += fabs(value[i][j]);
}
for (auto to : edges) {
auto a = to.first.first, b = to.first.second;
auto c = to.second;
auto rep = find(a);
if (fabs(c-value[a][j]-value[b][j]) > 1e-9) {
can[rep][j] = 0;
}
}
fill(all(used), 0);
for (auto to : reps) {
if (can[to][j]) {
if (acc[to].first > sum[to][j]) {
acc[to].first = sum[to][j];
acc[to].second = j;
}
}
}
}
int ans = 0;
for (auto to : reps) {
ans += acc[to].first;
}
if (ans >= 2e9) {
cout << "NO" << endl;
return;
}
cout << "YES" << endl;
for (int i = 1; i <= n; i++) {
cout << fixed << setprecision(6) << double(value[i][acc[find(i)].second])*.1 << ' ';
}
}
int main() {
//~ do_not_disturb
int t = 1;
//~ cin >> t;
while (t--) {
solve();
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
answer = YES |
2 |
Correct |
0 ms |
212 KB |
answer = YES |
3 |
Correct |
0 ms |
212 KB |
answer = YES |
4 |
Correct |
0 ms |
212 KB |
answer = NO |
5 |
Correct |
1 ms |
212 KB |
answer = YES |
6 |
Correct |
1 ms |
212 KB |
answer = YES |
7 |
Correct |
1 ms |
212 KB |
answer = YES |
8 |
Correct |
0 ms |
212 KB |
answer = YES |
9 |
Correct |
0 ms |
212 KB |
answer = NO |
10 |
Correct |
0 ms |
212 KB |
answer = YES |
11 |
Correct |
1 ms |
212 KB |
answer = YES |
12 |
Correct |
0 ms |
212 KB |
answer = NO |
13 |
Correct |
0 ms |
212 KB |
answer = YES |
14 |
Correct |
1 ms |
212 KB |
answer = YES |
15 |
Correct |
0 ms |
212 KB |
answer = YES |
16 |
Correct |
1 ms |
212 KB |
answer = YES |
17 |
Correct |
1 ms |
212 KB |
answer = YES |
18 |
Correct |
1 ms |
212 KB |
answer = YES |
19 |
Correct |
1 ms |
212 KB |
answer = YES |
20 |
Correct |
1 ms |
212 KB |
answer = YES |
21 |
Correct |
0 ms |
212 KB |
answer = YES |
22 |
Correct |
1 ms |
212 KB |
answer = NO |
23 |
Correct |
1 ms |
212 KB |
answer = NO |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
answer = YES |
2 |
Correct |
0 ms |
212 KB |
answer = YES |
3 |
Correct |
0 ms |
212 KB |
answer = YES |
4 |
Correct |
0 ms |
212 KB |
answer = NO |
5 |
Correct |
1 ms |
212 KB |
answer = YES |
6 |
Correct |
1 ms |
212 KB |
answer = YES |
7 |
Correct |
1 ms |
212 KB |
answer = YES |
8 |
Correct |
0 ms |
212 KB |
answer = YES |
9 |
Correct |
0 ms |
212 KB |
answer = NO |
10 |
Correct |
0 ms |
212 KB |
answer = YES |
11 |
Correct |
1 ms |
212 KB |
answer = YES |
12 |
Correct |
0 ms |
212 KB |
answer = NO |
13 |
Correct |
0 ms |
212 KB |
answer = YES |
14 |
Correct |
1 ms |
212 KB |
answer = YES |
15 |
Correct |
0 ms |
212 KB |
answer = YES |
16 |
Correct |
1 ms |
212 KB |
answer = YES |
17 |
Correct |
1 ms |
212 KB |
answer = YES |
18 |
Correct |
1 ms |
212 KB |
answer = YES |
19 |
Correct |
1 ms |
212 KB |
answer = YES |
20 |
Correct |
1 ms |
212 KB |
answer = YES |
21 |
Correct |
0 ms |
212 KB |
answer = YES |
22 |
Correct |
1 ms |
212 KB |
answer = NO |
23 |
Correct |
1 ms |
212 KB |
answer = NO |
24 |
Correct |
3 ms |
552 KB |
answer = YES |
25 |
Correct |
1 ms |
340 KB |
answer = YES |
26 |
Correct |
2 ms |
468 KB |
answer = YES |
27 |
Correct |
2 ms |
468 KB |
answer = YES |
28 |
Correct |
2 ms |
468 KB |
answer = YES |
29 |
Correct |
3 ms |
468 KB |
answer = YES |
30 |
Correct |
2 ms |
468 KB |
answer = NO |
31 |
Correct |
2 ms |
468 KB |
answer = YES |
32 |
Correct |
2 ms |
468 KB |
answer = YES |
33 |
Correct |
2 ms |
468 KB |
answer = YES |
34 |
Correct |
3 ms |
468 KB |
answer = YES |
35 |
Correct |
2 ms |
468 KB |
answer = YES |
36 |
Correct |
2 ms |
468 KB |
answer = YES |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
answer = YES |
2 |
Correct |
0 ms |
212 KB |
answer = YES |
3 |
Correct |
0 ms |
212 KB |
answer = YES |
4 |
Correct |
0 ms |
212 KB |
answer = NO |
5 |
Correct |
1 ms |
212 KB |
answer = YES |
6 |
Correct |
1 ms |
212 KB |
answer = YES |
7 |
Correct |
1 ms |
212 KB |
answer = YES |
8 |
Correct |
0 ms |
212 KB |
answer = YES |
9 |
Correct |
0 ms |
212 KB |
answer = NO |
10 |
Correct |
0 ms |
212 KB |
answer = YES |
11 |
Correct |
1 ms |
212 KB |
answer = YES |
12 |
Correct |
0 ms |
212 KB |
answer = NO |
13 |
Correct |
0 ms |
212 KB |
answer = YES |
14 |
Correct |
1 ms |
212 KB |
answer = YES |
15 |
Correct |
0 ms |
212 KB |
answer = YES |
16 |
Correct |
1 ms |
212 KB |
answer = YES |
17 |
Correct |
1 ms |
212 KB |
answer = YES |
18 |
Correct |
1 ms |
212 KB |
answer = YES |
19 |
Correct |
1 ms |
212 KB |
answer = YES |
20 |
Correct |
1 ms |
212 KB |
answer = YES |
21 |
Correct |
0 ms |
212 KB |
answer = YES |
22 |
Correct |
1 ms |
212 KB |
answer = NO |
23 |
Correct |
1 ms |
212 KB |
answer = NO |
24 |
Correct |
3 ms |
552 KB |
answer = YES |
25 |
Correct |
1 ms |
340 KB |
answer = YES |
26 |
Correct |
2 ms |
468 KB |
answer = YES |
27 |
Correct |
2 ms |
468 KB |
answer = YES |
28 |
Correct |
2 ms |
468 KB |
answer = YES |
29 |
Correct |
3 ms |
468 KB |
answer = YES |
30 |
Correct |
2 ms |
468 KB |
answer = NO |
31 |
Correct |
2 ms |
468 KB |
answer = YES |
32 |
Correct |
2 ms |
468 KB |
answer = YES |
33 |
Correct |
2 ms |
468 KB |
answer = YES |
34 |
Correct |
3 ms |
468 KB |
answer = YES |
35 |
Correct |
2 ms |
468 KB |
answer = YES |
36 |
Correct |
2 ms |
468 KB |
answer = YES |
37 |
Correct |
4 ms |
724 KB |
answer = YES |
38 |
Correct |
4 ms |
724 KB |
answer = YES |
39 |
Correct |
11 ms |
1696 KB |
answer = YES |
40 |
Correct |
19 ms |
2704 KB |
answer = YES |
41 |
Correct |
19 ms |
2644 KB |
answer = NO |
42 |
Correct |
19 ms |
2700 KB |
answer = YES |
43 |
Correct |
21 ms |
2772 KB |
answer = YES |
44 |
Correct |
20 ms |
2736 KB |
answer = YES |
45 |
Incorrect |
21 ms |
2852 KB |
jury has the better answer: jans = YES, pans = NO |
46 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
answer = YES |
2 |
Correct |
0 ms |
212 KB |
answer = YES |
3 |
Correct |
0 ms |
212 KB |
answer = YES |
4 |
Correct |
0 ms |
212 KB |
answer = NO |
5 |
Correct |
1 ms |
212 KB |
answer = YES |
6 |
Correct |
1 ms |
212 KB |
answer = YES |
7 |
Correct |
1 ms |
212 KB |
answer = YES |
8 |
Correct |
0 ms |
212 KB |
answer = YES |
9 |
Correct |
0 ms |
212 KB |
answer = NO |
10 |
Correct |
0 ms |
212 KB |
answer = YES |
11 |
Correct |
1 ms |
212 KB |
answer = YES |
12 |
Correct |
0 ms |
212 KB |
answer = NO |
13 |
Correct |
0 ms |
212 KB |
answer = YES |
14 |
Correct |
1 ms |
212 KB |
answer = YES |
15 |
Correct |
0 ms |
212 KB |
answer = YES |
16 |
Correct |
1 ms |
212 KB |
answer = YES |
17 |
Correct |
1 ms |
212 KB |
answer = YES |
18 |
Correct |
1 ms |
212 KB |
answer = YES |
19 |
Correct |
1 ms |
212 KB |
answer = YES |
20 |
Correct |
1 ms |
212 KB |
answer = YES |
21 |
Correct |
0 ms |
212 KB |
answer = YES |
22 |
Correct |
1 ms |
212 KB |
answer = NO |
23 |
Correct |
1 ms |
212 KB |
answer = NO |
24 |
Correct |
3 ms |
552 KB |
answer = YES |
25 |
Correct |
1 ms |
340 KB |
answer = YES |
26 |
Correct |
2 ms |
468 KB |
answer = YES |
27 |
Correct |
2 ms |
468 KB |
answer = YES |
28 |
Correct |
2 ms |
468 KB |
answer = YES |
29 |
Correct |
3 ms |
468 KB |
answer = YES |
30 |
Correct |
2 ms |
468 KB |
answer = NO |
31 |
Correct |
2 ms |
468 KB |
answer = YES |
32 |
Correct |
2 ms |
468 KB |
answer = YES |
33 |
Correct |
2 ms |
468 KB |
answer = YES |
34 |
Correct |
3 ms |
468 KB |
answer = YES |
35 |
Correct |
2 ms |
468 KB |
answer = YES |
36 |
Correct |
2 ms |
468 KB |
answer = YES |
37 |
Correct |
4 ms |
724 KB |
answer = YES |
38 |
Correct |
4 ms |
724 KB |
answer = YES |
39 |
Correct |
11 ms |
1696 KB |
answer = YES |
40 |
Correct |
19 ms |
2704 KB |
answer = YES |
41 |
Correct |
19 ms |
2644 KB |
answer = NO |
42 |
Correct |
19 ms |
2700 KB |
answer = YES |
43 |
Correct |
21 ms |
2772 KB |
answer = YES |
44 |
Correct |
20 ms |
2736 KB |
answer = YES |
45 |
Incorrect |
21 ms |
2852 KB |
jury has the better answer: jans = YES, pans = NO |
46 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
answer = YES |
2 |
Correct |
0 ms |
212 KB |
answer = YES |
3 |
Correct |
0 ms |
212 KB |
answer = YES |
4 |
Correct |
0 ms |
212 KB |
answer = NO |
5 |
Correct |
1 ms |
212 KB |
answer = YES |
6 |
Correct |
1 ms |
212 KB |
answer = YES |
7 |
Correct |
1 ms |
212 KB |
answer = YES |
8 |
Correct |
0 ms |
212 KB |
answer = YES |
9 |
Correct |
0 ms |
212 KB |
answer = NO |
10 |
Correct |
0 ms |
212 KB |
answer = YES |
11 |
Correct |
1 ms |
212 KB |
answer = YES |
12 |
Correct |
0 ms |
212 KB |
answer = NO |
13 |
Correct |
0 ms |
212 KB |
answer = YES |
14 |
Correct |
1 ms |
212 KB |
answer = YES |
15 |
Correct |
0 ms |
212 KB |
answer = YES |
16 |
Correct |
1 ms |
212 KB |
answer = YES |
17 |
Correct |
1 ms |
212 KB |
answer = YES |
18 |
Correct |
1 ms |
212 KB |
answer = YES |
19 |
Correct |
1 ms |
212 KB |
answer = YES |
20 |
Correct |
1 ms |
212 KB |
answer = YES |
21 |
Correct |
0 ms |
212 KB |
answer = YES |
22 |
Correct |
1 ms |
212 KB |
answer = NO |
23 |
Correct |
1 ms |
212 KB |
answer = NO |
24 |
Correct |
3 ms |
552 KB |
answer = YES |
25 |
Correct |
1 ms |
340 KB |
answer = YES |
26 |
Correct |
2 ms |
468 KB |
answer = YES |
27 |
Correct |
2 ms |
468 KB |
answer = YES |
28 |
Correct |
2 ms |
468 KB |
answer = YES |
29 |
Correct |
3 ms |
468 KB |
answer = YES |
30 |
Correct |
2 ms |
468 KB |
answer = NO |
31 |
Correct |
2 ms |
468 KB |
answer = YES |
32 |
Correct |
2 ms |
468 KB |
answer = YES |
33 |
Correct |
2 ms |
468 KB |
answer = YES |
34 |
Correct |
3 ms |
468 KB |
answer = YES |
35 |
Correct |
2 ms |
468 KB |
answer = YES |
36 |
Correct |
2 ms |
468 KB |
answer = YES |
37 |
Correct |
4 ms |
724 KB |
answer = YES |
38 |
Correct |
4 ms |
724 KB |
answer = YES |
39 |
Correct |
11 ms |
1696 KB |
answer = YES |
40 |
Correct |
19 ms |
2704 KB |
answer = YES |
41 |
Correct |
19 ms |
2644 KB |
answer = NO |
42 |
Correct |
19 ms |
2700 KB |
answer = YES |
43 |
Correct |
21 ms |
2772 KB |
answer = YES |
44 |
Correct |
20 ms |
2736 KB |
answer = YES |
45 |
Incorrect |
21 ms |
2852 KB |
jury has the better answer: jans = YES, pans = NO |
46 |
Halted |
0 ms |
0 KB |
- |