Submission #1306500

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306500		pvpro	Graph (BOI20_graph)	C++20	100 / 100	128 ms	26600 KiB

Graph

#ifndef LOCAL
#pragma GCC Optimize("O3,Ofast,unroll-loops")
#pragma GCC Target("bmi,bmi2,avx,avx2")
#endif
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

#define int ll

#define f first 
#define s second 
#define mp make_pair 
#define pb push_back
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin() (x).rend()
#ifndef LOCAL
#define endl "\n"
#endif

mt19937 rnd(11);

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<pii>> graph(n);
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        c *= 2;
        --a; --b;
        graph[a].pb(mp(b, c));
        graph[b].pb(mp(a, c));
    }
    vector<int> ans(n);
    vector<int> k(n), b(n);
    set<int> need;
    vector<int> ind;
    auto dfs = [&](int v, auto &&self) -> void {
        ind.pb(v);
        for (auto &u : graph[v]) {
            if (k[u.f] == 0) {
                k[u.f] = -k[v];
                b[u.f] = u.s - b[v];
                self(u.f, self);
            } else {
                if (k[u.f] != k[v]) {
                    if (b[u.f] + b[v] != u.s) {
                        need.insert(0);
                        need.insert(1);
                    }
                } else {
                    need.insert(k[v] * ((u.s - b[v] - b[u.f]) / 2)); 
                }
            }
        }
    };
    for (int i = 0; i < n; ++i) {
        if (k[i] == 0) {
            ind.clear();
            need.clear();
            k[i] = 1;
            dfs(i, dfs);
            if (need.size() > 1) {
                cout << "NO" << endl;
                return;
            }
            if (need.empty()) {
                vector<int> bplus, bminus;
                for (auto &x : ind) {
                    if (k[x] == 1) {
                        bplus.pb(b[x]);
                    } else {
                        bminus.pb(b[x]);
                    }
                }
                sort(all(bplus));
                sort(all(bminus));
                vector<int> Bplus = {0}, Bminus = {0};
                for (auto &x : bplus) {
                    Bplus.pb(Bplus.back() + x);
                }
                for (auto &x : bminus) {
                    Bminus.pb(Bminus.back() + x);
                }
                auto get = [&](int x) {
                    int ans = 0;
                    {
                        auto it = lower_bound(all(bplus), -x) - bplus.begin();
                        ans += (Bplus.back() - Bplus[it]) + (bplus.size() - it) * x - (it) * x - (Bplus[it]);
                    }
                    {
                        auto it = lower_bound(all(bminus), x) - bminus.begin();
                        ans += (Bminus.back() - Bminus[it]) - (bminus.size() - it) * x + (it) * x - (Bminus[it]);
                    }
                    return ans;
                };
                int l = -1e9, r = 1e9;
                while (r - l > 2) {
                    int m1 = (l * 2 + r) / 3;
                    int m2 = (l + 2 * r) / 3;
                    if (get(m1) < get(m2)) {
                        r = m2;
                    } else {
                        l = m1;
                    }
                }
                if (get(l) < get(l + 1) && get(l) < get(l + 2)) {
                    need.insert(l);
                } else if (get(l + 1) < get(l + 2)) {
                    need.insert(l + 1);
                } else {
                    need.insert(l + 2);
                }
            }
            for (auto &x : ind) {
                ans[x] = (*need.begin()) * k[x] + b[x];
            }
        }
    }
    cout << "YES" << endl;
    for (int i = 0; i < n; ++i) {
        cout << ((ld)ans[i]) / 2 << ' ';
    }
    cout << endl;
}

signed main() {
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #else
        ios::sync_with_stdio(false);
        cin.tie(0);
    #endif
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

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