Submission #874580

#	Time	Username	Problem	Language	Result	Execution time	Memory
874580		Stickfish	Cyberland (APIO23_cyberland)	C++17	44 / 100	31 ms	11096 KiB

cyberland

#include "cyberland.h"
#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]});
    }
}

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;
    bitset<MAXN> start;
    for (int i = 0; i < N; ++i) {
        start[i] = used[i] & (i == 0 || arr[i] == 0);
    }
    int K0 = 0;
    for (int i = 0; i < N; ++i) {
        if (arr[i] == 2 && used[i])
            ++K0;
    }
    K = min(K, K0);
    if (K > 0 && M == N - 1) {
        for (int i = 0; i < M - 1; ++i) {
            assert(x[i] == i && y[i] == i + 1);
        }
        double ans = 0;
        double mod = 1;
        int cnt = 0;
        for (int i = H - 1; i >= 0; --i) {
            ans += 1.0 * mod * c[i];
            if (arr[i] == 2 && cnt < K) {
                ++cnt;
                mod /= 2;
            }
            if (start[i])
                return ans;
        }
        assert(0);
    }
    vector<double> depth(N, INF);
    depth[H] = 0;
    set<pair<double, int>> pq;
    used = 0;
    pq.insert({depth[H], H});
    while (pq.size()) {
        auto [d, v] = *pq.begin();
        if (start[v])
            return d;
        pq.erase(pq.begin());
        for (auto [u, len] : edg[v]) {
            if (d + len < depth[u]) {
                pq.erase({depth[u], u});
                depth[u] = d + len;
                pq.insert({depth[u], u});
            }
        }
    }
    vector<pair<double, int>> rdepth;
    for (int i = 0; i < N; ++i) {
        if (depth[i] < INF / 2) {
            rdepth.push_back({depth[i], i});
        }
    }
    sort(rdepth.begin(), rdepth.end());
    return -1;
}

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