Submission #1172146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172146		nrg_studio	Graph (BOI20_graph)	C++20	100 / 100	82 ms	18368 KiB

Graph

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define chmin(a, b) a = min(a,b)
#define chmax(a, b) a = max(a,b)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define all(x) x.begin(),x.end()
#define vec vector

const int MAX_N = 1e5;
vec<pii> adj[MAX_N];
int ans[MAX_N];
int col[MAX_N] = {0};
vec<pii> comps;
vec<vec<int>> comps2;

void dfs(int cur, int color) {
    col[cur] = color+1;
    comps2.back().pb(cur);
    for (auto[x,c] : adj[cur]) {
        if (!col[x]) {
            ans[x] = c-ans[cur];
            dfs(x,!color);
        } else {
            if (col[x]==col[cur]) {
                comps.back().f = cur;
                comps.back().s = (c-ans[cur]-ans[x])/2;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    int n, m; cin >> n >> m;
    for (int i=0;i<m;i++) {
        int a, b, c; cin >> a >> b >> c;
        adj[--a].pb({--b,2*c});
        adj[b].pb({a,2*c});
    }
    for (int i=0;i<n;i++) {
        if (!col[i]) {
            comps.pb({-1,-1});
            comps2.pb({});
            dfs(i,0);
        }
    }
    for (int c=0;c<comps.size();c++) {
        auto[rt,delta] = comps[c];
        if (rt==-1) {
            rt = comps2[c][0];
            vec<int> idx;
            for (int i : comps2[c]) {
                if (col[i]==col[rt]) {idx.pb(-ans[i]);}
                else {idx.pb(ans[i]);}
            }
            sort(all(idx));
            delta = idx[(idx.size()-1)/2];
        }
        for (int i : comps2[c]) {
            ans[i] += (col[i]==col[rt] ? 1 : -1)*delta;
        }
    }

    bool flag = false;
    for (int i=0;i<n;i++) {
        for (auto[x,c] : adj[i]) {
            if (ans[x]+ans[i]!=c) {flag = true;}
        }
    }

    if (flag) {cout << "NO\n";}
    else {
        cout << "YES\n";
        cout << fixed << setprecision(1);
        for (int i=0;i<n;i++) {
            cout << (double)ans[i]/2 << ' ';
        }
    }

}

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