# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
604815 |
2022-07-25T10:05:43 Z |
OttoTheDino |
Graph (BOI20_graph) |
C++17 |
|
2 ms |
2680 KB |
#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,e) for (int i = s; i <= e; ++i)
#define rrep(i,s,e) for (int i = s; i >= e; --i)
#define pb push_back
#define pf push_front
#define all(a) a.begin(), a.end()
#define len(a) (int)a.size()
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<pll> vpll;
const int mx = 1e5;
const double eps = 1e-9;
vii adj[mx+1];
int b1[mx+1], b2[mx+1], b3[mx+1], c[mx+1];
double ans[mx+1];
double eq (double x, double y) {
return abs(x-y)<eps;
}
pair<int,double> dfs1 (int u, int p) {
b1[u] = 1;
for (ii ve : adj[u]) {
int v = ve.fi, e = ve.se;
if (e==p) continue;
if (b1[v]) {
if (u==v) return {u,{c[e]/2.0}};
return {v,c[e]};
}
pair<int,double> res = dfs1 (v,e);
if (res.fi) {
res.se = c[e]-res.se;
if (u==res.fi) return {u,res.se/2.0};
return {res.fi,res.se};
}
}
return {0,0};
}
void dfs_help (int u) {
b3[u] = b1[u] = 1;
for (ii ve : adj[u]) {
int v = ve.fi;
if (b3[v]) continue;
dfs_help (v);
}
}
double dfs2 (int u, int p, double val) {
double s = 0;
b2[u] = 1;
ans[u] = val;
for (ii ve : adj[u]) {
int v = ve.fi, e = ve.se;
if (e==p) continue;
if (b2[v]) {
if (!eq(c[e],val+ans[v])) {
return 1e9;
}
continue;
}
double res = dfs2 (v, e, c[e]-val);
if (res==1e9) return 1e9;
s += res;
}
return s+abs(val);
}
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m; cin >> n >> m;
rep (i,1,m) {
int u, v; cin >> u >> v;
adj[u].pb({v,i});
adj[v].pb({u,i});
cin >> c[i];
}
bool suc = 1;
rep (i,1,n) {
if (!b1[i]) {
pair<int,double> res = dfs1 (i,0);
if (res.fi) {
dfs_help(i);
if (dfs2 (1,-1,res.se)==1e9) {
suc = 0;
break;
}
}
else {
double a = dfs2 (1,-1,0), b = dfs2 (1,-1,1), z = dfs2 (1,-1,2);
double mi = min(a,min(b,z));
if (mi==1e9) {
suc = 0;
break;
}
if (a==mi) dfs2 (1,-1,0);
else if (b==mi) dfs2 (1,-1,1);
else dfs2 (1,-1,2);
}
}
}
if (suc) {
cout << "YES\n";
rep (i,1,n) cout << ans[i] << " \n"[i==n];
}
else cout << "NO\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
answer = YES |
2 |
Correct |
2 ms |
2680 KB |
answer = YES |
3 |
Correct |
2 ms |
2644 KB |
answer = YES |
4 |
Correct |
2 ms |
2644 KB |
answer = NO |
5 |
Incorrect |
2 ms |
2644 KB |
Sum of endpoints for edge (5; 3) differs from the expected value 2. |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
answer = YES |
2 |
Correct |
2 ms |
2680 KB |
answer = YES |
3 |
Correct |
2 ms |
2644 KB |
answer = YES |
4 |
Correct |
2 ms |
2644 KB |
answer = NO |
5 |
Incorrect |
2 ms |
2644 KB |
Sum of endpoints for edge (5; 3) differs from the expected value 2. |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
answer = YES |
2 |
Correct |
2 ms |
2680 KB |
answer = YES |
3 |
Correct |
2 ms |
2644 KB |
answer = YES |
4 |
Correct |
2 ms |
2644 KB |
answer = NO |
5 |
Incorrect |
2 ms |
2644 KB |
Sum of endpoints for edge (5; 3) differs from the expected value 2. |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
answer = YES |
2 |
Correct |
2 ms |
2680 KB |
answer = YES |
3 |
Correct |
2 ms |
2644 KB |
answer = YES |
4 |
Correct |
2 ms |
2644 KB |
answer = NO |
5 |
Incorrect |
2 ms |
2644 KB |
Sum of endpoints for edge (5; 3) differs from the expected value 2. |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
answer = YES |
2 |
Correct |
2 ms |
2680 KB |
answer = YES |
3 |
Correct |
2 ms |
2644 KB |
answer = YES |
4 |
Correct |
2 ms |
2644 KB |
answer = NO |
5 |
Incorrect |
2 ms |
2644 KB |
Sum of endpoints for edge (5; 3) differs from the expected value 2. |
6 |
Halted |
0 ms |
0 KB |
- |