oj.uz

Submission #604829

# Submission time Handle Problem Language Result Execution time Memory
604829 2022-07-25T10:11:18 Z OttoTheDino Graph (BOI20_graph) C++17
0 / 100
 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];

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;

    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);
            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 (a==mi) dfs2 (1,-1,0);
                else if (b==mi) dfs2 (1,-1,1);
                else dfs2 (1,-1,2);
            }
        }
    }

    rep (i,1,m) {
        if (!eq(ans[edges[i].fi]+ans[edges[i].se], c[i])){ suc = 0;
        break;
        }
    }

    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 2 ms 2644 KB answer = YES
2 Correct 3 ms 2644 KB answer = YES
3 Correct 2 ms 2644 KB answer = YES
4 Correct 2 ms 2644 KB answer = NO
5 Incorrect 1 ms 2644 KB jury has the better answer: jans = YES, pans = NO
6 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB answer = YES
2 Correct 3 ms 2644 KB answer = YES
3 Correct 2 ms 2644 KB answer = YES
4 Correct 2 ms 2644 KB answer = NO
5 Incorrect 1 ms 2644 KB jury has the better answer: jans = YES, pans = NO
6 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB answer = YES
2 Correct 3 ms 2644 KB answer = YES
3 Correct 2 ms 2644 KB answer = YES
4 Correct 2 ms 2644 KB answer = NO
5 Incorrect 1 ms 2644 KB jury has the better answer: jans = YES, pans = NO
6 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB answer = YES
2 Correct 3 ms 2644 KB answer = YES
3 Correct 2 ms 2644 KB answer = YES
4 Correct 2 ms 2644 KB answer = NO
5 Incorrect 1 ms 2644 KB jury has the better answer: jans = YES, pans = NO
6 Halted 0 ms 0 KB -

Subtask #5
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB answer = YES
2 Correct 3 ms 2644 KB answer = YES
3 Correct 2 ms 2644 KB answer = YES
4 Correct 2 ms 2644 KB answer = NO
5 Incorrect 1 ms 2644 KB jury has the better answer: jans = YES, pans = NO
6 Halted 0 ms 0 KB -