Submission #1182357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182357		qwusha	Graph (BOI20_graph)	C++20	34 / 100	706 ms	28012 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);
        }
    }
}

int K = 400;



signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    g.resize(n);
    unordered_map<int, int> mp;
    for (int i = 0; i < m; i++) {
        int v, u, w;
        cin >> v >> u >> w;
        if (mp.find((v - 1) * 1e7 + (u - 1)) != mp.end()) {
            if (mp[(v - 1) * 1e7 + (u - 1)] != w * 2) {
                cout << "NO" << '\n';
                return 0;
            }
        } else {
            mp[(v - 1) * 1e7 + (u - 1)] = w * 2;
            mp[(u - 1) * 1e7 + (v - 1)] = w * 2;
        }
        g[v - 1].push_back({u - 1, w * 2});
        g[u - 1].push_back({v - 1, w * 2});
    }
    vector<int> indbig(n, -1);
    map<int, int> indnorm;
    int B = 0;
    for (int i = 0; i < n; i++) {
        if (g[i].size() > K) {
            indbig[i] = B;
            indnorm[B] = i;
            B++;
        }
    }
    vector<vector<pair<int, int>>> gB(B);
    for (int i = 0; i < n; i++) {
        if (indbig[i] == -1)
            continue;
        for (auto [u, q] : g[i]) {
            if (indbig[u] != -1) {
                gB[indbig[i]].push_back({indbig[u], q});
            }
        }
    }
    vector<pair<int, int>> know;
    for (int i = 0; i < n; i++) {
        if (indbig[i] == -1) {
            for (auto [j, w1] : g[i]) {
                for (auto [q, w2] : g[i]) {
                    if (j == q)
                        continue;
                    if (mp.find(j * 1e7 + q) != mp.end()) {
                        int w3 = mp[j * 1e7 + q];
                        if (w1 != w2 || w2 != w3 || w1 != w3) {
                            if (w1 + w2 + w3 == 8) {
                                if (w1 == 4)
                                    know.push_back({q, 0});
                                else if (w2 == 4)
                                    know.push_back({j, 0});
                                else
                                    know.push_back({i, 0});
                            } else {
                                if (w1 == 2)
                                    know.push_back({q, 3});
                                else if (w2 == 2)
                                    know.push_back({j, 3});
                                else
                                    know.push_back({i, 3});
                            }
                        }
                    }
                }
            }
        }
    }
    if (1) {
        for (int i = 0; i < B; i++) {
            for (int j = i + 1; j < B; j++) {
                int ni = indnorm[i], nj = indnorm[j];
                if (mp.find(ni * 1e7 + nj) == mp.end())
                    continue;
                for (int q = j + 1; q < B; q++) {
                    int nq = indnorm[q];
                    if (mp.find(ni * 1e7 + nq) != mp.end() && mp.find(nq * 1e7 + nj) != mp.end()) {
                        int w1 = mp[ni * 1e7 + nj];
                        int w2 = mp[ni * 1e7 + nq];
                        int w3 = mp[nj * 1e7 + nq];
                        if (w1 + w2 + w3 == 8) {
                            if (w1 == 4)
                                know.push_back({nq, 0});
                            else if (w2 == 4)
                                know.push_back({nj, 0});
                            else
                                know.push_back({ni, 0});
                        } else {
                            if (w1 == 2)
                                know.push_back({nq, 3});
                            else if (w2 == 2)
                                know.push_back({nj, 3});
                            else
                                know.push_back({ni, 3});
                        }
                    }
                }
            }
        }
    }
    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);
    }
    vector<pair<int, int>> known(boss.size(), {-1, -1});
    for (auto par : know) {
        known[col[par.fi]] = par;
    }
    val.assign(n, inf);
    bool done = 1;
    int answer = 0;
    vector<pair<int, int>> bq(boss.size());
    vector<int> num(boss.size());
    for (int i = 0; i < boss.size(); i++) {
        double r = (double)comps[i].size() / (double)n;
        num[i] = max(1ll, (int)(r * 8));
    }
    for (int co = 0; co < boss.size(); co++) {
        bool ok = 0;
        int indb = -1;
        curbest = inf;
        int bst = -1;
        if (known[co].fi != -1) {
            int st = known[co].fi;
            int stval = known[co].se;
            nowsum = 0;
            for (auto el : chan) {
                val[el] = inf;
            }
            chan.clear();
            if (dfs(st, stval)) {
                ok = 1;
                if (nowsum < curbest) {
                    curbest = nowsum;
                    indb = stval;
                    bst = st;
                }
            }
        } else {
            for (int qw = 0; qw < num[co]; qw++) {
                int st = comps[co][rnd() % comps[co].size()];
                int l = -8, r = 15;
                if (comps.size() > n / 10) {
                    l = -18;
                    r = 25;
                }
                if (comps.size() > n / 2) {
                    l = -28;
                    r = 35;
                }
                for (int q = 0; q <= r; 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;
                        }
                    }

                }

                for (int q = -1; q >= l; 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: 0 / 24
• Subtask 4: 0 / 42
• Subtask 5: 5 / 5