| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 604892 |
2022-07-25T10:38:37 Z |
OttoTheDino |
Graph (BOI20_graph) |
C++17 |
|
3 ms |
2644 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];
vi cur;
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};
}
int dfs_help (int u, int d) {
int res = d;
b3[u] = b1[u] = 1;
cur.pb(u);
for (ii ve : adj[u]) {
int v = ve.fi;
if (b3[v]) continue;
res = max(res, dfs_help (v,d+1));
}
return res;
}
double dfs2 (int u, int p, double val) {
double s = abs(val);
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;
}
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m; cin >> n >> m;
ii edges[m+1];
rep (i,1,m) {
int u, v; cin >> u >> v;
adj[u].pb({v,i});
adj[v].pb({u,i});
cin >> c[i];
edges[i] = {u,v};
}
bool suc = 1;
rep (i,1,n) {
if (!b1[i]) {
pair<int,double> res = dfs1 (i,0);
int dep = dfs_help(i,1);
if (res.fi) {
if (dfs2 (i,-1,res.se)==1e9) {
suc = 0;
break;
}
}
else {
double mis[16*dep+1];
int id = 0;
rep (j,0,16*dep) {
mis[j] = dfs2 (i,-1,j-8*dep);
if (mis[j]<mis[id]) id =j;
for (int el : cur) b2[el] = 0;
}
dfs2(i,-1,id-8*dep);
}
cur.clear();
}
}
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 |
1 ms |
2644 KB |
answer = YES |
| 3 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 4 |
Correct |
1 ms |
2644 KB |
answer = NO |
| 5 |
Correct |
1 ms |
2644 KB |
answer = YES |
| 6 |
Correct |
3 ms |
2644 KB |
answer = YES |
| 7 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 8 |
Incorrect |
2 ms |
2644 KB |
participant answer is larger than the answer of jury |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 2 |
Correct |
1 ms |
2644 KB |
answer = YES |
| 3 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 4 |
Correct |
1 ms |
2644 KB |
answer = NO |
| 5 |
Correct |
1 ms |
2644 KB |
answer = YES |
| 6 |
Correct |
3 ms |
2644 KB |
answer = YES |
| 7 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 8 |
Incorrect |
2 ms |
2644 KB |
participant answer is larger than the answer of jury |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 2 |
Correct |
1 ms |
2644 KB |
answer = YES |
| 3 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 4 |
Correct |
1 ms |
2644 KB |
answer = NO |
| 5 |
Correct |
1 ms |
2644 KB |
answer = YES |
| 6 |
Correct |
3 ms |
2644 KB |
answer = YES |
| 7 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 8 |
Incorrect |
2 ms |
2644 KB |
participant answer is larger than the answer of jury |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 2 |
Correct |
1 ms |
2644 KB |
answer = YES |
| 3 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 4 |
Correct |
1 ms |
2644 KB |
answer = NO |
| 5 |
Correct |
1 ms |
2644 KB |
answer = YES |
| 6 |
Correct |
3 ms |
2644 KB |
answer = YES |
| 7 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 8 |
Incorrect |
2 ms |
2644 KB |
participant answer is larger than the answer of jury |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 2 |
Correct |
1 ms |
2644 KB |
answer = YES |
| 3 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 4 |
Correct |
1 ms |
2644 KB |
answer = NO |
| 5 |
Correct |
1 ms |
2644 KB |
answer = YES |
| 6 |
Correct |
3 ms |
2644 KB |
answer = YES |
| 7 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 8 |
Incorrect |
2 ms |
2644 KB |
participant answer is larger than the answer of jury |
| 9 |
Halted |
0 ms |
0 KB |
- |
