#include <bits/stdc++.h>
using namespace std;
using ld = long double;
class dsu {
public:
vector<int> p, h;
int n, nCC;
dsu() {}
dsu(int _n) : n(_n), nCC(n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
h.assign(n, 0);
}
void init(int _n) {
n = _n;
nCC = n;
p.resize(n);
iota(p.begin(), p.end(), 0);
h.assign(n, 0);
}
inline int get(int x) {
return (x == p[x] ? x : (p[x] = get(p[x])));
}
inline bool same(int x, int y) {
return get(x) == get(y);
}
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x == y) {
return false;
}
--nCC;
if (h[x] > h[y]) {
swap(x, y);
}
p[x] = y;
h[y] += (h[x] == h[y]);
return true;
}
};
const int N = (int) 2e5 + 9;
const ld inf = (ld) 1e7 + 9;
ld vals[] = {-2, -1.5, -1, -.5, 0, .5, 1, 1.5, 2};
int n, m, vis[N];
ld a[N], finalV[N], S[N];
map<int, ld> W[N];
vector<pair<int, ld>> g[N];
vector<int> comps[N];
ld dfs(int v) {
vis[v] = 1;
ld ret = fabsl(a[v]);
for (auto [u, w] : g[v]) {
if (vis[u]) {
if (a[u] + a[v] != w) {
return inf;
}
continue;
}
a[u] = w - a[v];
ret += dfs(u);
if (ret >= inf) {
return inf;
}
}
return ret;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
fill(S, S + n, -1);
dsu se(n);
set<pair<int, int>> see;
for (int i = 0; i < m; i++) {
int u, v;
ld w;
cin >> u >> v >> w;
--u; --v;
if (u == v && S[v] != -1) {
if (S[v] != w) {
cout << "NO" << '\n';
return 0;
}
}
if (u == v) {
S[v] = w;
}
if (see.count({u, v})) {
if (W[u][v] != w) {
cout << "NO" << '\n';
return 0;
}
} else {
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
W[u][v] = w;
W[v][u] = w;
see.insert({u, v});
see.insert({v, u});
se.unite(u, v);
}
for (int i = 0; i < n; i++) {
comps[se.get(i)].push_back(i);
}
for (int i = 0; i < n; i++) {
if (comps[i].empty() || vis[i]) {
continue;
}
int start = comps[i][0];
ld ans = -1;
for (ld x : vals) {
a[start] = x;
for (int u : comps[i]) {
vis[u] = 0;
}
ld z = dfs(start);
if (z < inf && (ans == -1 || z < ans)) {
ans = z;
for (int u : comps[i]) {
finalV[u] = a[u];
}
}
}
if (ans == -1) {
cout << "NO" << '\n';
return 0;
}
}
cout << "YES" << '\n';
for (int i = 0; i < n; i++) {
if (i > 0) {
cout << " ";
}
cout << finalV[i];
}
cout << '\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
19024 KB |
answer = YES |
2 |
Correct |
8 ms |
19020 KB |
answer = YES |
3 |
Correct |
8 ms |
19112 KB |
answer = YES |
4 |
Correct |
8 ms |
19040 KB |
answer = NO |
5 |
Correct |
9 ms |
19148 KB |
answer = YES |
6 |
Correct |
9 ms |
19020 KB |
answer = YES |
7 |
Correct |
9 ms |
19020 KB |
answer = YES |
8 |
Correct |
9 ms |
19112 KB |
answer = YES |
9 |
Correct |
9 ms |
19020 KB |
answer = NO |
10 |
Correct |
9 ms |
19148 KB |
answer = YES |
11 |
Correct |
11 ms |
19200 KB |
answer = YES |
12 |
Correct |
10 ms |
19020 KB |
answer = NO |
13 |
Correct |
8 ms |
19100 KB |
answer = YES |
14 |
Correct |
9 ms |
19108 KB |
answer = YES |
15 |
Correct |
9 ms |
19020 KB |
answer = YES |
16 |
Correct |
9 ms |
19040 KB |
answer = YES |
17 |
Correct |
9 ms |
19112 KB |
answer = YES |
18 |
Correct |
9 ms |
19148 KB |
answer = YES |
19 |
Correct |
9 ms |
19100 KB |
answer = YES |
20 |
Correct |
9 ms |
19116 KB |
answer = YES |
21 |
Correct |
9 ms |
19148 KB |
answer = YES |
22 |
Correct |
8 ms |
19020 KB |
answer = NO |
23 |
Correct |
8 ms |
19116 KB |
answer = NO |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
19024 KB |
answer = YES |
2 |
Correct |
8 ms |
19020 KB |
answer = YES |
3 |
Correct |
8 ms |
19112 KB |
answer = YES |
4 |
Correct |
8 ms |
19040 KB |
answer = NO |
5 |
Correct |
9 ms |
19148 KB |
answer = YES |
6 |
Correct |
9 ms |
19020 KB |
answer = YES |
7 |
Correct |
9 ms |
19020 KB |
answer = YES |
8 |
Correct |
9 ms |
19112 KB |
answer = YES |
9 |
Correct |
9 ms |
19020 KB |
answer = NO |
10 |
Correct |
9 ms |
19148 KB |
answer = YES |
11 |
Correct |
11 ms |
19200 KB |
answer = YES |
12 |
Correct |
10 ms |
19020 KB |
answer = NO |
13 |
Correct |
8 ms |
19100 KB |
answer = YES |
14 |
Correct |
9 ms |
19108 KB |
answer = YES |
15 |
Correct |
9 ms |
19020 KB |
answer = YES |
16 |
Correct |
9 ms |
19040 KB |
answer = YES |
17 |
Correct |
9 ms |
19112 KB |
answer = YES |
18 |
Correct |
9 ms |
19148 KB |
answer = YES |
19 |
Correct |
9 ms |
19100 KB |
answer = YES |
20 |
Correct |
9 ms |
19116 KB |
answer = YES |
21 |
Correct |
9 ms |
19148 KB |
answer = YES |
22 |
Correct |
8 ms |
19020 KB |
answer = NO |
23 |
Correct |
8 ms |
19116 KB |
answer = NO |
24 |
Correct |
9 ms |
19148 KB |
answer = YES |
25 |
Correct |
9 ms |
19148 KB |
answer = YES |
26 |
Incorrect |
9 ms |
19148 KB |
participant answer is larger than the answer of jury |
27 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
19024 KB |
answer = YES |
2 |
Correct |
8 ms |
19020 KB |
answer = YES |
3 |
Correct |
8 ms |
19112 KB |
answer = YES |
4 |
Correct |
8 ms |
19040 KB |
answer = NO |
5 |
Correct |
9 ms |
19148 KB |
answer = YES |
6 |
Correct |
9 ms |
19020 KB |
answer = YES |
7 |
Correct |
9 ms |
19020 KB |
answer = YES |
8 |
Correct |
9 ms |
19112 KB |
answer = YES |
9 |
Correct |
9 ms |
19020 KB |
answer = NO |
10 |
Correct |
9 ms |
19148 KB |
answer = YES |
11 |
Correct |
11 ms |
19200 KB |
answer = YES |
12 |
Correct |
10 ms |
19020 KB |
answer = NO |
13 |
Correct |
8 ms |
19100 KB |
answer = YES |
14 |
Correct |
9 ms |
19108 KB |
answer = YES |
15 |
Correct |
9 ms |
19020 KB |
answer = YES |
16 |
Correct |
9 ms |
19040 KB |
answer = YES |
17 |
Correct |
9 ms |
19112 KB |
answer = YES |
18 |
Correct |
9 ms |
19148 KB |
answer = YES |
19 |
Correct |
9 ms |
19100 KB |
answer = YES |
20 |
Correct |
9 ms |
19116 KB |
answer = YES |
21 |
Correct |
9 ms |
19148 KB |
answer = YES |
22 |
Correct |
8 ms |
19020 KB |
answer = NO |
23 |
Correct |
8 ms |
19116 KB |
answer = NO |
24 |
Correct |
9 ms |
19148 KB |
answer = YES |
25 |
Correct |
9 ms |
19148 KB |
answer = YES |
26 |
Incorrect |
9 ms |
19148 KB |
participant answer is larger than the answer of jury |
27 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
19024 KB |
answer = YES |
2 |
Correct |
8 ms |
19020 KB |
answer = YES |
3 |
Correct |
8 ms |
19112 KB |
answer = YES |
4 |
Correct |
8 ms |
19040 KB |
answer = NO |
5 |
Correct |
9 ms |
19148 KB |
answer = YES |
6 |
Correct |
9 ms |
19020 KB |
answer = YES |
7 |
Correct |
9 ms |
19020 KB |
answer = YES |
8 |
Correct |
9 ms |
19112 KB |
answer = YES |
9 |
Correct |
9 ms |
19020 KB |
answer = NO |
10 |
Correct |
9 ms |
19148 KB |
answer = YES |
11 |
Correct |
11 ms |
19200 KB |
answer = YES |
12 |
Correct |
10 ms |
19020 KB |
answer = NO |
13 |
Correct |
8 ms |
19100 KB |
answer = YES |
14 |
Correct |
9 ms |
19108 KB |
answer = YES |
15 |
Correct |
9 ms |
19020 KB |
answer = YES |
16 |
Correct |
9 ms |
19040 KB |
answer = YES |
17 |
Correct |
9 ms |
19112 KB |
answer = YES |
18 |
Correct |
9 ms |
19148 KB |
answer = YES |
19 |
Correct |
9 ms |
19100 KB |
answer = YES |
20 |
Correct |
9 ms |
19116 KB |
answer = YES |
21 |
Correct |
9 ms |
19148 KB |
answer = YES |
22 |
Correct |
8 ms |
19020 KB |
answer = NO |
23 |
Correct |
8 ms |
19116 KB |
answer = NO |
24 |
Correct |
9 ms |
19148 KB |
answer = YES |
25 |
Correct |
9 ms |
19148 KB |
answer = YES |
26 |
Incorrect |
9 ms |
19148 KB |
participant answer is larger than the answer of jury |
27 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
19024 KB |
answer = YES |
2 |
Correct |
8 ms |
19020 KB |
answer = YES |
3 |
Correct |
8 ms |
19112 KB |
answer = YES |
4 |
Correct |
8 ms |
19040 KB |
answer = NO |
5 |
Correct |
9 ms |
19148 KB |
answer = YES |
6 |
Correct |
9 ms |
19020 KB |
answer = YES |
7 |
Correct |
9 ms |
19020 KB |
answer = YES |
8 |
Correct |
9 ms |
19112 KB |
answer = YES |
9 |
Correct |
9 ms |
19020 KB |
answer = NO |
10 |
Correct |
9 ms |
19148 KB |
answer = YES |
11 |
Correct |
11 ms |
19200 KB |
answer = YES |
12 |
Correct |
10 ms |
19020 KB |
answer = NO |
13 |
Correct |
8 ms |
19100 KB |
answer = YES |
14 |
Correct |
9 ms |
19108 KB |
answer = YES |
15 |
Correct |
9 ms |
19020 KB |
answer = YES |
16 |
Correct |
9 ms |
19040 KB |
answer = YES |
17 |
Correct |
9 ms |
19112 KB |
answer = YES |
18 |
Correct |
9 ms |
19148 KB |
answer = YES |
19 |
Correct |
9 ms |
19100 KB |
answer = YES |
20 |
Correct |
9 ms |
19116 KB |
answer = YES |
21 |
Correct |
9 ms |
19148 KB |
answer = YES |
22 |
Correct |
8 ms |
19020 KB |
answer = NO |
23 |
Correct |
8 ms |
19116 KB |
answer = NO |
24 |
Correct |
9 ms |
19148 KB |
answer = YES |
25 |
Correct |
9 ms |
19148 KB |
answer = YES |
26 |
Incorrect |
9 ms |
19148 KB |
participant answer is larger than the answer of jury |
27 |
Halted |
0 ms |
0 KB |
- |