| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 467331 |
2021-08-22T16:19:30 Z |
MVP_Harry |
Graph (BOI20_graph) |
C++17 |
|
2 ms |
2636 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) 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 |
Incorrect |
2 ms |
2636 KB |
Sum of endpoints for edge (2; 1) differs from the expected value 1. |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
Incorrect |
2 ms |
2636 KB |
Sum of endpoints for edge (2; 1) differs from the expected value 1. |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
Incorrect |
2 ms |
2636 KB |
Sum of endpoints for edge (2; 1) differs from the expected value 1. |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
Incorrect |
2 ms |
2636 KB |
Sum of endpoints for edge (2; 1) differs from the expected value 1. |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
Incorrect |
2 ms |
2636 KB |
Sum of endpoints for edge (2; 1) differs from the expected value 1. |
| 5 |
Halted |
0 ms |
0 KB |
- |
