제출 #604818

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
604818		OttoTheDino	Graph (BOI20_graph)	C++17	0 / 100	2 ms	2644 KiB

Graph

#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;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 12
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 42