Submission #977389

#	Time	Username	Problem	Language	Result	Execution time	Memory
977389		faruk	Cyberland (APIO23_cyberland)	C++17	100 / 100	1103 ms	80840 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()

using namespace std;

const double INF = 1e18;

struct edge {
    double cost;
    int t;
    int inc;
    edge() {}
    edge(double cost, int t, bool inc) : cost(cost), t(t), inc(inc) { }
};

struct node {
    double cost;
    int idx, uses;
    node() {}
    node(double cost, int idx, int uses) : cost(cost), idx(idx), uses(uses) {

    }

    bool operator<(const node &b) const {
        return cost > b.cost;
    }
};

const int maxK = 80;

vector<vector<edge> > graph;
vector<int> type;
vector<double> pow2(maxK + 1);
int n, m, k, h;

vector<vector<double> > dijkstra() {
    int myk = min(k, maxK);
    vector<vector<double> > dist(n, vector<double>(myk + 1, INF));
    dist[h][0] = 0;
    priority_queue<node> q;
    q.push(node(0, h, 0));
    while (!q.empty()) {
        node me = q.top(); q.pop();
        if (dist[me.idx][me.uses] < me.cost || (me.idx == h and me.uses != 0))
            continue;
        for (auto &[cst, to, typ] : graph[me.idx]) {
            if (me.uses + typ > myk)
                continue;
            double new_cst = cst / pow2[me.uses] + me.cost;
            if (dist[to][me.uses + typ] > new_cst) {
                dist[to][me.uses + typ] = new_cst;
                q.push(node(new_cst, to, me.uses + typ));
            }
        }
    }
    return dist;
}

vector<bool> vis;
void dfs(int curr) {
    vis[curr] = true;
    if (curr == h)
        return;
    for (auto &[cst, to, typ] : graph[curr])
        if (!vis[to])
            dfs(to);
}

double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
    n = N, m = M, k = K, h = H;
    pow2[0] = 1;
    for (int i = 1; i <= maxK; i++)
        pow2[i] = pow2[i - 1] * 2.0;
    type = arr;
    vis = vector<bool> (n);
    graph = vector<vector<edge> > (n);
    for (int i = 0; i < m; i++) {
        graph[x[i]].push_back(edge(c[i], y[i], 0));
        graph[y[i]].push_back(edge(c[i], x[i], 0));
        if (type[y[i]] == 2)
            graph[x[i]].push_back(edge(c[i], y[i], 1));
        if (type[x[i]] == 2)
            graph[y[i]].push_back(edge(c[i], x[i], 1));
    }

    dfs(0);
    if (!vis[h])
        return -1;

    vector<vector<double> > dist = dijkstra();
    double out = *min_element(all(dist[0]));
    for (int i = 1; i < n; i++)
    {
        if (arr[i] == 0 and vis[i])
            out = min(out, *min_element(all(dist[i])));
    }

    return out;
}

• 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