oj.uz

Submission #604884

# Submission time Handle Problem Language Result Execution time Memory
604884 2022-07-25T10:36:17 Z OttoTheDino Graph (BOI20_graph) C++17
0 / 100
 2 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[8*dep+1];
                int id =  0;
                rep (j,0,8*dep) {
                    mis[j] = dfs2 (i,-1,j-4*dep);
                    if (mis[j]<mis[id]) id =j;
                    for (int el : cur) b2[el] = 0;
                }
                dfs2(i,-1,id-2*dep);
            }
            cur.clear();
        }
    }

    if (suc) {
        cout << "YES\n";
        rep (i,1,n) cout << ans[i] << " \n"[i==n];
    }
    else cout << "NO\n";

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB answer = YES
2 Incorrect 2 ms 2644 KB participant answer is larger than the answer of jury
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB answer = YES
2 Incorrect 2 ms 2644 KB participant answer is larger than the answer of jury
3 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB answer = YES
2 Incorrect 2 ms 2644 KB participant answer is larger than the answer of jury
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB answer = YES
2 Incorrect 2 ms 2644 KB participant answer is larger than the answer of jury
3 Halted 0 ms 0 KB -

Subtask #5
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB answer = YES
2 Incorrect 2 ms 2644 KB participant answer is larger than the answer of jury
3 Halted 0 ms 0 KB -