Submission #957519

#	Time	Username	Problem	Language	Result	Execution time	Memory
957519		Pring	Cyberland (APIO23_cyberland)	C++17	68 / 100	1042 ms	227380 KiB

cyberland

#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

// #define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;
typedef pair<double, int> pdi;
using ll = __int128_t;

namespace {
    const int MXN = 100005, MXK = 35;
    int n, m, k, h;
    vector<int> u, v, w, a;
    vector<pdi> edge[MXN * MXK];
    double dis[MXN * MXK];
    vector<int> zero;
    bitset<MXN> b;

    inline int f(int x, int y) {
        return x * n + y;
    }

    void build_graph1() {
        FOR(i, 0, m) {
            int x = u[i], y = v[i];
            double z = w[i];
            if (x != h) edge[x].push_back(mp(z, y));
            if (y != h) edge[y].push_back(mp(z, x));
        }
    }

    void DFS(int id) {
        b[id] = true;
        for (auto &[w, i] : edge[id]) {
            if (b[i]) continue;
            DFS(i);
        }
    }

    void find_zero() {
        zero.clear();
        zero.push_back(1);
        FOR(i, 1, n + 1) b[i] = 0;
        DFS(1);
        FOR(i, 1, n + 1) if (a[i] == 0 && b[i]) zero.push_back(i);
    }

    void cls_graph() {
        FOR(i, 1, n + 1) edge[i].clear();
    }

    void build_graph2() {
        auto PUT = [&](int x, int y, double z) -> void {
            if (a[x] == 2) {
                FOR(i, 0, k) edge[f(i, x)].push_back(mp(z * (2LL << i), f(i + 1, y)));;
            } else {
                FOR(i, 0, k + 1) edge[f(i, x)].push_back(mp(z * (1LL << i), f(i, y)));
            }
        };
        for (auto &i : zero) edge[0].push_back(mp(0.0, i));
        FOR(i, 0, m) {
            int x = u[i], y = v[i];
            double z = w[i];
            if (x != h) PUT(x, y, z);
            if (y != h) PUT(y, x, z);
        }
    }

    void DIJKSTRA() {
        priority_queue<pdi, vector<pdi>, greater<pdi>> pq;
        fill(dis, dis + n * k + n + 1, 3.9e239);
        pq.push(mp(0.0, 0));
        while (pq.size()) {
            auto [len, id] = pq.top();
            pq.pop();
            if (dis[id] < 3.9e239) continue;
            dis[id] = len;
            for (auto &[w, i] : edge[id]) {
                if (dis[i] < 3.9e239) continue;
                pq.push(mp(len + w, i));
            }
        }
    }

    void RESET() {
        FOR(i, 0, n * (k + 1) + 1) edge[i].clear();
    }

    double APIO() {
        assert(k <= 30);
        build_graph1();
        find_zero();
        cls_graph();
        build_graph2();
        DIJKSTRA();
        double ans = 3.9e239;
        FOR(i, 0, k + 1) {
            ans = min(ans, dis[f(i, h)] / (1LL << i));
        }
        RESET();
        return (ans >= 2e18 ? -1.0 : ans);
    }
}

double solve(int N, int M, int K, int H, vector<int> U, vector<int> V, vector<int> W, vector<int> A) {
    H++;
    for (auto &i : U) i++;
    for (auto &i : V) i++;
    A.insert(A.begin(), 0);
    ::n = N;
    ::m = M;
    ::k = K;
    ::h = H;
    ::u = U;
    ::v = V;
    ::w = W;
    ::a = A;
    return APIO();
}

#ifdef MIKU
void READ(vector<int> &v) {
    int n;
    cin >> n;
    v.resize(n);
    for (auto &i : v) cin >> i;
}

void miku() {
    int n, m, k, h;
    vector<int> u, v, w, a;
    cin >> n >> m >> k >> h;
    READ(u);
    READ(v);
    READ(w);
    READ(a);
    cout << solve(n, m, k, h, u, v, w, a) << '\n';
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}
#endif

• 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: 0 / 29
• Subtask 8: 0 / 3