Submission #1359387

#TimeUsernameProblemLanguageResultExecution timeMemory
1359387Joshua_AnderssonGraph (BOI20_graph)C++20
58 / 100
572 ms38096 KiB
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vi = vector<ll>;
using vvi = vector<vi>;
using p2 = pair<ll, ll>;
const ll inf = 1e18;

#define rep(i,n) for (ll i = 0; i < (n); i++)
#define repp(i,a,n) for (ll i = (a); i < (n); i++)
#define repe(i, arr) for (auto& i : arr)
#define all(x) begin(x),end(x)
#define sz(x) ((ll)(x).size())

void die() {
    cout << "NO\n";
    exit(0);
}

void dfs(int u, int p, vi& vis, vi& nodeval, vi& dep, vector<double>& compvals, vi& comp, vector<vector<p2>>& adj) {
    comp.push_back(u);
    vis[u]=1;
    dep[u]=dep[p]+1;

    repe(e, adj[u]) {
        if (e.first==p) continue;
        if (vis[e.first]) {
            // cout << "non-tree:" << u << " " << e.first << '\n';
            // even dep: +x
            // odd  dep: -x
            if (dep[u]%2 != dep[e.first]%2) {
                if (nodeval[u]+nodeval[e.first]!=e.second) {
                    
                    // cout << u << " " << e.first << " " << nodeval[u] << " " << nodeval[e.first] << '\n';
                    // cerr << "DIE 2" << endl;
                    die();
                }
            }
            else {
                if (dep[u]%2==1) {
                    // cout << "odd dep" << '\n';
                    compvals.emplace_back((-e.second+nodeval[u]+nodeval[e.first])/2.0);
                }
                else {
                    // cout << "even dep" << '\n';
                    compvals.emplace_back((e.second-nodeval[u]-nodeval[e.first])/2.0);
                }
            }
        }
        else {
            nodeval[e.first] = e.second-nodeval[u];
            dfs(e.first,u,vis,nodeval,dep,compvals,comp,adj);
        }
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int n,m;
    cin >> n >> m;
    vector<vector<p2>> adj(n);
    map<p2,int> color;
    vvi self_edges(n);
    vector<tuple<int,int,int>> edges;
    rep(i,m) {
        int a,b,c;
        cin >> a >> b >> c;
        a--; b--;
        edges.emplace_back(a,b,c);
        if (a==b) {
            self_edges[a].push_back(c);
            continue;
        }
        if (a>b) swap(a,b);
        if (color.count(p2(a,b))) {
            if (color[p2(a,b)]!=c) {
                // cerr << "DIE 1" << endl;
                die();
            }
        }
        else {
            adj[a].emplace_back(b,c);
            adj[b].emplace_back(a,c);
        }
        color[p2(a,b)]=c;
    }

    vi order;
    rep(i,n) {
        if (sz(self_edges[i])) order.push_back(i);
    }
    rep(i,n) {
        if (!sz(self_edges[i])) order.push_back(i);
    }

    vi vis(n);

    vi nodeval(n);
    vi dep(n);
    vector<double> ans(n);
    repe(i,order) {
        if (vis[i]) continue;
        vector<double> compvals;
        dep[i]=-1;
        vi comp;
        auto get = [&](int u, double x) {
            if (dep[u]%2==0) return x+nodeval[u];
            return -x+nodeval[u];
        };
        dfs(i,i,vis,nodeval,dep,compvals,comp,adj);
        if (sz(self_edges[i])) {
            compvals.push_back(self_edges[i][0]/2.0);
        }
        if (sz(compvals)) {
            if (sz(compvals)>1) {
                double v1 = compvals[0];
                repe(u,compvals) {
                    cerr << "Compval 1: " << compvals[0] << ", compval 2: " << u << '\n';
                    if (abs(u-v1)>1e-8) {
                        die();
                    }
                }
            }
            repe(u,comp) {
                ans[u]=get(u,compvals[0]);
            }
        }
        else {
            
            auto cost = [&](double x) {
                double ret = 0;
                repe(u,comp) ret += abs(get(u, x));
                return ret;
            };

            double lo = -1e6;
            double hi = 1e6;
            rep(i,100) {
                double l1 = lo+(hi-lo)/3;
                double r1 = hi-(hi-lo)/3;
                if (cost(l1)<cost(r1)) {
                    hi = r1;
                }
                else {
                    lo=l1;
                }
            }

            repe(u,comp) {
                ans[u]=get(u,lo);
            }
        }
    }


    // int eind = 0;
    // for (auto [a,b,c] : edges) {
    //     if (!abs(ans[a]+ans[b]-c)<1e-6) {
    //         cerr << "fail" << eind << '\n';
    //         return 0;
    //     }
    //     eind++;
    // }

    cout << "YES\n";
    cout << fixed << setprecision(15);
    repe(u,ans) {
        cout << u << " ";
    }
    cout << '\n';


    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...