Submission #1182305

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182305		qwusha	Graph (BOI20_graph)	C++20	58 / 100	251 ms	16476 KiB

Graph

#include <bits/stdc++.h>
using namespace std;
/*
#pragma GCC optimize("O3")
#include <bitset>
#pragma GCC target("avx2")*/
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double ld;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
int inf = 1e15;


vector<vector<pair<int, int>>> g;
vector<int> val;
int curbest = inf;
int nowsum = 0;
vector<int> chan;

bool dfs(int v, int q) {
    chan.push_back(v);
    val[v] = q;
    nowsum += abs(q);
    if (nowsum >= curbest)
        return 0;
    for (auto [u, w] : g[v]) {
        if (val[u] != inf) {
            if (val[u] + val[v] != w)
                return 0;
        } else {
            int res = dfs(u, w - val[v]);
            if (res == 0)
                return 0;
        }
    }
    return 1;
}

vector<int> col;

void dfs_comp(int v, int c) {
    col[v] = c;
    for (auto [u, w] : g[v]) {
        if (col[u] == -1) {
            dfs_comp(u, c);
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    g.resize(n);
    for (int i = 0; i < m; i++) {
        int v, u, w;
        cin >> v >> u >> w;
        g[v - 1].push_back({u - 1, w * 2});
        g[u - 1].push_back({v - 1, w * 2});
    }
    col.resize(n, -1);
    vector<int> boss;
    for (int i = 0; i < n; i++) {
        if (col[i] == -1) {
            boss.push_back(i);
            dfs_comp(i, boss.size() - 1);
        }
    }
    vector<vector<int>> comps(boss.size());
    for (int i = 0; i < n; i++) {
        comps[col[i]].push_back(i);
    }
    val.assign(n, inf);
    bool done = 1;
    int answer = 0;
    vector<pair<int, int>> bq(boss.size());
    int totalstuff = 50;
    vector<int> num(boss.size());
    for (int i = 0; i < boss.size(); i++) {
        double r = (double)comps[i].size() / (double)n;
        num[i] = min(3ll, max(1ll, (int)(r * 5)));
    }
    for (int co = 0; co < boss.size(); co++) {
        bool ok = 0;
        int indb = -1;
        curbest = inf;
        int bst = -1;
        for (int qw = 0; qw < num[co]; qw++) {
            int st = comps[co][rnd() % comps[co].size()];
            for (int q = -25; q <= 30; q++) {
                nowsum = 0;
                for (auto el : chan) {
                    val[el] = inf;
                }
                chan.clear();
                if (dfs(st, q)) {
                    ok = 1;
                    if (nowsum < curbest) {
                        curbest = nowsum;
                        indb = q;
                        bst = st;
                    }
                }

            }
        }
        bq[co] = {indb, bst};
        if (ok == 0) {
            done = 0;
            break;
        }
        answer += curbest;
    }
    if (done == 0) {
        cout << "NO" << '\n';
        return 0;
    } else {
        cout << "YES" << '\n';
        for (int i = 0; i < n; i++) {
            val[i] = inf;
        }
        curbest = inf;
        nowsum = 0;
        for (int co = 0; co < boss.size(); co++) {
            dfs(bq[co].se, bq[co].fi);
        }
        for (auto el : val) {
            cout << el * 0.5 << ' ';
        }
        cout << '\n';
    }


}

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