| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 467332 |
2021-08-22T16:20:49 Z |
MVP_Harry |
Graph (BOI20_graph) |
C++17 |
|
193 ms |
19944 KB |
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define rep(i, m, n) for (int i = m; i <= n; i++)
#define per(i, m, n) for (int i = m; i >= n; i--)
#define sz(v) (int) v.size()
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int maxn = 1e5 + 5;
const double eps = 1e-6;
int N, M, leader, impossible, cycle = 0;
int vis[maxn];
double a[maxn];
vector<pair<int, int> > G[maxn];
vector<int> pt;
pair<int, int> c[maxn];
void dfs1(int u, int par) {
vis[u] = 2;
for (auto node : G[u]) {
int v = node.fi, x = node.se;
if (v == par) continue;
if (vis[v] == 2) {
// consider c[u], c[v]
if (c[u].se + c[v].se == 0) {
if (c[u].fi + c[v].fi != x) impossible = 1;
else continue;
}
cycle = 1;
double val = (double) (x - c[u].fi - c[v].fi) / (c[u].se + c[v].se);
if (a[leader] == INF) a[leader] = val;
else {
if (abs(a[leader] - val) > eps) impossible = 1;
}
} else {
c[v] = mp(x - c[u].fi, -c[u].se);
dfs1(v, u);
}
}
}
void dfs2(int u, int par) {
vis[u] = 3;
pt.push_back((-c[u].se) * c[u].fi);
for (auto node : G[u]) {
if (node.fi == par || vis[node.fi] == 3) continue;
dfs2(node.fi, u);
}
}
void dfs3(int u, int par) {
vis[u] = 1;
if (u != leader) a[u] = (double) c[u].fi + (double) c[u].se * a[leader];
for (auto node : G[u]) {
if (node.fi == par || vis[node.fi] == 1) continue;
dfs3(node.fi, u);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> N >> M;
rep(i, 1, M) {
int u, v, x;
cin >> u >> v >> x;
G[u].push_back(mp(v, x)), G[v].push_back(mp(u, x));
}
rep(i, 1, N) a[i] = INF;
rep(i, 1, N) if (!vis[i]) {
c[i] = mp(0, 1);
leader = i, cycle = 0;
dfs1(i, 0);
if (impossible) {
cout << "NO\n";
return 0;
}
if (!cycle) {
pt.clear();
dfs2(i, 0);
sort(all(pt));
a[leader] = pt[(sz(pt) - 1) / 2];
}
dfs3(i, 0);
}
cout << "YES\n";
rep(i, 1, N) cout << a[i] << " ";
cout << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 2 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 3 |
Correct |
2 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 |
2 ms |
2636 KB |
answer = NO |
| 10 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 11 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 12 |
Correct |
2 ms |
2636 KB |
answer = NO |
| 13 |
Correct |
2 ms |
2676 KB |
answer = YES |
| 14 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 15 |
Correct |
2 ms |
2688 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 |
2 ms |
2636 KB |
answer = YES |
| 20 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 21 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 22 |
Correct |
2 ms |
2636 KB |
answer = NO |
| 23 |
Correct |
2 ms |
2636 KB |
answer = NO |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 2 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 3 |
Correct |
2 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 |
2 ms |
2636 KB |
answer = NO |
| 10 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 11 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 12 |
Correct |
2 ms |
2636 KB |
answer = NO |
| 13 |
Correct |
2 ms |
2676 KB |
answer = YES |
| 14 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 15 |
Correct |
2 ms |
2688 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 |
2 ms |
2636 KB |
answer = YES |
| 20 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 21 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 22 |
Correct |
2 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 |
2 ms |
2680 KB |
answer = YES |
| 28 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 29 |
Correct |
2 ms |
2676 KB |
answer = YES |
| 30 |
Correct |
2 ms |
2676 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 |
2 ms |
2636 KB |
answer = YES |
| 35 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 36 |
Correct |
2 ms |
2636 KB |
answer = YES |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 2 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 3 |
Correct |
2 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 |
2 ms |
2636 KB |
answer = NO |
| 10 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 11 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 12 |
Correct |
2 ms |
2636 KB |
answer = NO |
| 13 |
Correct |
2 ms |
2676 KB |
answer = YES |
| 14 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 15 |
Correct |
2 ms |
2688 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 |
2 ms |
2636 KB |
answer = YES |
| 20 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 21 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 22 |
Correct |
2 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 |
2 ms |
2680 KB |
answer = YES |
| 28 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 29 |
Correct |
2 ms |
2676 KB |
answer = YES |
| 30 |
Correct |
2 ms |
2676 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 |
2 ms |
2636 KB |
answer = YES |
| 35 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 36 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 37 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 38 |
Correct |
2 ms |
2672 KB |
answer = YES |
| 39 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 40 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 41 |
Correct |
2 ms |
2636 KB |
answer = NO |
| 42 |
Correct |
3 ms |
2764 KB |
answer = YES |
| 43 |
Correct |
3 ms |
2636 KB |
answer = YES |
| 44 |
Correct |
3 ms |
2636 KB |
answer = YES |
| 45 |
Correct |
3 ms |
2636 KB |
answer = YES |
| 46 |
Correct |
2 ms |
2764 KB |
answer = YES |
| 47 |
Correct |
4 ms |
2636 KB |
answer = YES |
| 48 |
Correct |
3 ms |
2636 KB |
answer = YES |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 2 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 3 |
Correct |
2 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 |
2 ms |
2636 KB |
answer = NO |
| 10 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 11 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 12 |
Correct |
2 ms |
2636 KB |
answer = NO |
| 13 |
Correct |
2 ms |
2676 KB |
answer = YES |
| 14 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 15 |
Correct |
2 ms |
2688 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 |
2 ms |
2636 KB |
answer = YES |
| 20 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 21 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 22 |
Correct |
2 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 |
2 ms |
2680 KB |
answer = YES |
| 28 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 29 |
Correct |
2 ms |
2676 KB |
answer = YES |
| 30 |
Correct |
2 ms |
2676 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 |
2 ms |
2636 KB |
answer = YES |
| 35 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 36 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 37 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 38 |
Correct |
2 ms |
2672 KB |
answer = YES |
| 39 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 40 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 41 |
Correct |
2 ms |
2636 KB |
answer = NO |
| 42 |
Correct |
3 ms |
2764 KB |
answer = YES |
| 43 |
Correct |
3 ms |
2636 KB |
answer = YES |
| 44 |
Correct |
3 ms |
2636 KB |
answer = YES |
| 45 |
Correct |
3 ms |
2636 KB |
answer = YES |
| 46 |
Correct |
2 ms |
2764 KB |
answer = YES |
| 47 |
Correct |
4 ms |
2636 KB |
answer = YES |
| 48 |
Correct |
3 ms |
2636 KB |
answer = YES |
| 49 |
Correct |
11 ms |
3436 KB |
answer = YES |
| 50 |
Correct |
14 ms |
3580 KB |
answer = YES |
| 51 |
Correct |
11 ms |
3788 KB |
answer = YES |
| 52 |
Correct |
6 ms |
3588 KB |
answer = NO |
| 53 |
Correct |
3 ms |
2636 KB |
answer = YES |
| 54 |
Correct |
4 ms |
2764 KB |
answer = YES |
| 55 |
Correct |
6 ms |
3092 KB |
answer = YES |
| 56 |
Correct |
11 ms |
3472 KB |
answer = YES |
| 57 |
Correct |
11 ms |
3324 KB |
answer = YES |
| 58 |
Correct |
11 ms |
3276 KB |
answer = YES |
| 59 |
Correct |
10 ms |
3276 KB |
answer = YES |
| 60 |
Correct |
11 ms |
3404 KB |
answer = YES |
| 61 |
Correct |
6 ms |
3020 KB |
answer = YES |
| 62 |
Correct |
73 ms |
10176 KB |
answer = NO |
| 63 |
Correct |
91 ms |
10244 KB |
answer = YES |
| 64 |
Correct |
72 ms |
10124 KB |
answer = NO |
| 65 |
Correct |
78 ms |
10180 KB |
answer = YES |
| 66 |
Correct |
4 ms |
2764 KB |
answer = YES |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 2 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 3 |
Correct |
2 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 |
2 ms |
2636 KB |
answer = NO |
| 10 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 11 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 12 |
Correct |
2 ms |
2636 KB |
answer = NO |
| 13 |
Correct |
2 ms |
2676 KB |
answer = YES |
| 14 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 15 |
Correct |
2 ms |
2688 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 |
2 ms |
2636 KB |
answer = YES |
| 20 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 21 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 22 |
Correct |
2 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 |
2 ms |
2680 KB |
answer = YES |
| 28 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 29 |
Correct |
2 ms |
2676 KB |
answer = YES |
| 30 |
Correct |
2 ms |
2676 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 |
2 ms |
2636 KB |
answer = YES |
| 35 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 36 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 37 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 38 |
Correct |
2 ms |
2672 KB |
answer = YES |
| 39 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 40 |
Correct |
2 ms |
2636 KB |
answer = YES |
| 41 |
Correct |
2 ms |
2636 KB |
answer = NO |
| 42 |
Correct |
3 ms |
2764 KB |
answer = YES |
| 43 |
Correct |
3 ms |
2636 KB |
answer = YES |
| 44 |
Correct |
3 ms |
2636 KB |
answer = YES |
| 45 |
Correct |
3 ms |
2636 KB |
answer = YES |
| 46 |
Correct |
2 ms |
2764 KB |
answer = YES |
| 47 |
Correct |
4 ms |
2636 KB |
answer = YES |
| 48 |
Correct |
3 ms |
2636 KB |
answer = YES |
| 49 |
Correct |
11 ms |
3436 KB |
answer = YES |
| 50 |
Correct |
14 ms |
3580 KB |
answer = YES |
| 51 |
Correct |
11 ms |
3788 KB |
answer = YES |
| 52 |
Correct |
6 ms |
3588 KB |
answer = NO |
| 53 |
Correct |
3 ms |
2636 KB |
answer = YES |
| 54 |
Correct |
4 ms |
2764 KB |
answer = YES |
| 55 |
Correct |
6 ms |
3092 KB |
answer = YES |
| 56 |
Correct |
11 ms |
3472 KB |
answer = YES |
| 57 |
Correct |
11 ms |
3324 KB |
answer = YES |
| 58 |
Correct |
11 ms |
3276 KB |
answer = YES |
| 59 |
Correct |
10 ms |
3276 KB |
answer = YES |
| 60 |
Correct |
11 ms |
3404 KB |
answer = YES |
| 61 |
Correct |
6 ms |
3020 KB |
answer = YES |
| 62 |
Correct |
73 ms |
10176 KB |
answer = NO |
| 63 |
Correct |
91 ms |
10244 KB |
answer = YES |
| 64 |
Correct |
72 ms |
10124 KB |
answer = NO |
| 65 |
Correct |
78 ms |
10180 KB |
answer = YES |
| 66 |
Correct |
4 ms |
2764 KB |
answer = YES |
| 67 |
Correct |
98 ms |
16132 KB |
answer = YES |
| 68 |
Correct |
94 ms |
16016 KB |
answer = YES |
| 69 |
Correct |
90 ms |
15408 KB |
answer = YES |
| 70 |
Correct |
131 ms |
19944 KB |
answer = YES |
| 71 |
Correct |
93 ms |
15728 KB |
answer = YES |
| 72 |
Correct |
120 ms |
10340 KB |
answer = YES |
| 73 |
Correct |
107 ms |
9848 KB |
answer = YES |
| 74 |
Correct |
66 ms |
10180 KB |
answer = YES |
| 75 |
Correct |
32 ms |
10024 KB |
answer = NO |
| 76 |
Correct |
13 ms |
3532 KB |
answer = YES |
| 77 |
Correct |
27 ms |
4640 KB |
answer = YES |
| 78 |
Correct |
46 ms |
6068 KB |
answer = YES |
| 79 |
Correct |
96 ms |
9308 KB |
answer = YES |
| 80 |
Correct |
73 ms |
10584 KB |
answer = YES |
| 81 |
Correct |
48 ms |
12316 KB |
answer = NO |
| 82 |
Correct |
107 ms |
15216 KB |
answer = YES |
| 83 |
Correct |
124 ms |
15684 KB |
answer = YES |
| 84 |
Correct |
141 ms |
16120 KB |
answer = YES |
| 85 |
Correct |
100 ms |
16188 KB |
answer = YES |
| 86 |
Correct |
93 ms |
15572 KB |
answer = YES |
| 87 |
Correct |
58 ms |
10820 KB |
answer = NO |
| 88 |
Correct |
127 ms |
12204 KB |
answer = YES |
| 89 |
Correct |
105 ms |
9284 KB |
answer = YES |
| 90 |
Correct |
105 ms |
9488 KB |
answer = YES |
| 91 |
Correct |
102 ms |
9288 KB |
answer = YES |
| 92 |
Correct |
52 ms |
6344 KB |
answer = YES |
| 93 |
Correct |
48 ms |
6240 KB |
answer = YES |
| 94 |
Correct |
62 ms |
15260 KB |
answer = NO |
| 95 |
Correct |
48 ms |
9040 KB |
answer = NO |
| 96 |
Correct |
193 ms |
17560 KB |
answer = YES |
| 97 |
Correct |
45 ms |
15216 KB |
answer = NO |
