Submission #604889

#	Time	Username	Problem	Language	Result	Execution time	Memory
604889		OttoTheDino	Graph (BOI20_graph)	C++17	0 / 100	3 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];
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[4*dep+1];
                int id =  0;
                rep (j,0,4*dep) {
                    mis[j] = dfs2 (i,-1,j-2*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
• Subtask 2: 0 / 12
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 42