Submission #874620

#	Time	Username	Problem	Language	Result	Execution time	Memory
874620		Stickfish	Cyberland (APIO23_cyberland)	C++17	100 / 100	2782 ms	13952 KiB

cyberland

#include "cyberland.h"
#include <cmath>
#include <vector>
#include <cassert>
#include <algorithm>
#include <set>
#include <bitset>
using namespace std;

const int MAXN = 1e5 + 123;
const double INF = 1e18 + 177013;
vector<pair<int, int>> edg[MAXN];
bitset<MAXN> used;

void dfs_connect(int v, int H) {
    if (used[v])
        return;
    used[v] = 1;
    if (v == H)
        return;
    for (auto [u, d] : edg[v]) {
        dfs_connect(u, H);
    }
}

void initialize(int N, int M, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    for (int i = 0; i < N; ++i) {
        edg[i].clear();
    }
    used = 0;
    for (int i = 0; i < M; ++i) {
        edg[x[i]].push_back({y[i], c[i]});
        edg[y[i]].push_back({x[i], c[i]});
    }
}

vector<double> bfs(int N, const vector<pair<double, int>>& inits, double mod) {
    vector<double> depth(N, INF);
    set<pair<double, int>> rdepth;
    used = 0;
    for (const auto &[d, v] : inits) {
        depth[v] = d;
        rdepth.insert({d, v});
    }
    while (rdepth.size()) {
        const auto [d, v] = *rdepth.begin();
        rdepth.erase(rdepth.begin());
        for (auto [u, len] : edg[v]) {
            if (d + len * mod < depth[u]) {
                rdepth.erase({depth[u], u});
                depth[u] = d + len * mod;
                rdepth.insert({depth[u], u});
            }
        }
    }
    return depth;
}

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    initialize(N, M, x, y, c, arr);
    dfs_connect(0, H);
    if (!used[H])
        return -1;
    double __end_mod = 1;
    if (arr[H] == 0)
        return 0;
    if (arr[H] == 2 && K > 0) {
        arr[H] = 1;
        --K;
        __end_mod = 0.5;
    }

    bitset<MAXN> start;
    for (int i = 0; i < N; ++i) {
        start[i] = used[i] & (i == 0 || arr[i] == 0);
    }
    bitset<MAXN> div2;
    for (int i = 0; i < N; ++i) {
        div2[i] = arr[i] == 2 && used[i];
    }
    K = min({K, 120});
    vector<double> depth;
    double ans = INF;
    depth = bfs(N, {{0, H}}, 1);
    for (int i = start._Find_first(); i < N; i = start._Find_next(i))
        ans = min(ans, depth[i]);

    for (auto [u, d] : edg[H]) {
        edg[u].erase(find(edg[u].begin(), edg[u].end(), pair<int, int>(H, d)));
    }

    for (int ki = 1; ki <= K; ++ki) {
        vector<pair<double, int>> pts;
        for (int i = div2._Find_first(); i < N; i = div2._Find_next(i)) {
            pts.push_back({depth[i], i});
        }
        double mod = pow(0.5, ki);
        depth = bfs(N, pts, mod);
        for (int i = start._Find_first(); i < N; i = start._Find_next(i))
            ans = min(ans, depth[i]);
        vector<double> ndepth(N, INF);
        for (int i = div2._Find_first(); i < N; i = div2._Find_next(i)) {
            for (auto [u, d] : edg[i])
                ndepth[i] = min(ndepth[i], depth[u] + d * mod);
        }
        for (int i = div2._Find_first(); i < N; i = div2._Find_next(i)) {
            depth[i] = ndepth[i];
        }
    }
    return ans * __end_mod;
}

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 29 / 29
• Subtask 8: 3 / 3