| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1030453 |
2024-07-22T05:23:46 Z |
thinknoexit |
Graph (BOI20_graph) |
C++17 |
|
2 ms |
2820 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100100;
struct A {
int v, w;
};
vector<A> adj[N];
double ans[N];
bool ch[N], vis[N];
int col[N], bp = 0;
vector<pair<int, int>> cycle;
void dfs(int v, vector<int>& node) {
node.push_back(v);
vis[v] = 1;
for (auto& x : adj[v]) {
if (!vis[x.v]) dfs(x.v, node);
}
}
void dfs_ans(int v) {
for (auto& x : adj[v]) {
if (!ch[x.v]) {
ch[x.v] = 1;
ans[x.v] = x.w - ans[v];
dfs_ans(x.v);
}
}
}
bool bipartite(int v, int c) {
if (col[v]) {
if (col[v] != c) return bp = v, false;
else return true;
}
col[v] = c;
for (auto& x : adj[v]) {
if (!bipartite(x.v, 3 - c)) {
if (bp != 0) cycle.push_back({ v, x.w });
if (v == bp) bp = 0;
return false;
}
}
return true;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, m;
cin >> n >> m;
for (int i = 1;i <= m;i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({ v, w });
adj[v].push_back({ u, w });
}
for (int i = 1;i <= n;i++) {
if (vis[i]) continue;
vector<int> node;
dfs(i, node);
bool bipar = bipartite(i, 1);
if (!bipar) {
vector<pair<int, int>> c = cycle;
cycle.clear();
int root = c.back().first;
int val = 0;
for (int i = 0;i < (int)c.size();i++) {
if (i & 1) val -= c[i].second;
else val += c[i].second;
}
// value at node (root) = val / 2
ch[root] = 1;
ans[root] = (double)val / 2;
dfs_ans(root);
continue;
}
if ((int)node.size() == 1) {
continue;
}
// try V
double mn = 1e9;
int idx = -1;
for (int V = -4;V <= 4;V++) {
ch[i] = 1;
ans[i] = (double)V / 2;
dfs_ans(i);
int sum = 0;
bool can = 1;
for (auto& i : node) {
ch[i] = 0;
sum += ans[i];
for (auto& x : adj[i]) {
if (ans[i] + ans[x.v] != x.w) {
can = 0;
break;
}
}
if (!can) break;
}
if (can) {
if (sum < mn) {
mn = sum;
idx = V;
}
}
}
if (mn == 1e9) {
cout << "NO";
return 0;
}
ch[i] = 1;
ans[i] = idx;
dfs_ans(i);
}
for (int i = 1;i <= n;i++) {
for (auto& x : adj[i]) {
if (ans[i] + ans[x.v] != x.w) {
cout << "NO";
return 0;
}
}
}
cout << "YES\n";
for (int i = 1;i <= n;i++) {
cout << ans[i] << ' ';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2648 KB |
answer = YES |
| 2 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 3 |
Incorrect |
2 ms |
2820 KB |
participant answer is larger than the answer of jury |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2648 KB |
answer = YES |
| 2 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 3 |
Incorrect |
2 ms |
2820 KB |
participant answer is larger than the answer of jury |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2648 KB |
answer = YES |
| 2 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 3 |
Incorrect |
2 ms |
2820 KB |
participant answer is larger than the answer of jury |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2648 KB |
answer = YES |
| 2 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 3 |
Incorrect |
2 ms |
2820 KB |
participant answer is larger than the answer of jury |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2648 KB |
answer = YES |
| 2 |
Correct |
1 ms |
2652 KB |
answer = YES |
| 3 |
Incorrect |
2 ms |
2820 KB |
participant answer is larger than the answer of jury |
| 4 |
Halted |
0 ms |
0 KB |
- |
