oj.uz

Submission #977389

# Submission time Handle Problem Language Result Execution time Memory
977389 2024-05-07T20:39:06 Z faruk Cyberland (APIO23_cyberland) C++17
100 / 100
 1103 ms 80840 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 600 KB Correct.
2 Correct 17 ms 604 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 860 KB Correct.
2 Correct 24 ms 852 KB Correct.
3 Correct 23 ms 832 KB Correct.
4 Correct 24 ms 860 KB Correct.
5 Correct 25 ms 912 KB Correct.
6 Correct 21 ms 4256 KB Correct.
7 Correct 36 ms 4000 KB Correct.
8 Correct 13 ms 8024 KB Correct.
9 Correct 23 ms 348 KB Correct.
10 Correct 23 ms 348 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 784 KB Correct.
2 Correct 25 ms 780 KB Correct.
3 Correct 22 ms 856 KB Correct.
4 Correct 24 ms 348 KB Correct.
5 Correct 24 ms 348 KB Correct.
6 Correct 5 ms 3416 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 23900 KB Correct.
2 Correct 108 ms 856 KB Correct.
3 Correct 99 ms 884 KB Correct.
4 Correct 104 ms 828 KB Correct.
5 Correct 117 ms 548 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 836 KB Correct.
2 Correct 23 ms 828 KB Correct.
3 Correct 22 ms 860 KB Correct.
4 Correct 22 ms 3928 KB Correct.
5 Correct 20 ms 544 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 844 KB Correct.
2 Correct 19 ms 716 KB Correct.
3 Correct 32 ms 8832 KB Correct.
4 Correct 14 ms 2856 KB Correct.
5 Correct 22 ms 348 KB Correct.
6 Correct 21 ms 804 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 844 KB Correct.
2 Correct 16 ms 856 KB Correct.
3 Correct 526 ms 28500 KB Correct.
4 Correct 202 ms 7376 KB Correct.
5 Correct 429 ms 20168 KB Correct.
6 Correct 179 ms 10968 KB Correct.
7 Correct 200 ms 7188 KB Correct.
8 Correct 186 ms 1696 KB Correct.
9 Correct 86 ms 876 KB Correct.
10 Correct 78 ms 768 KB Correct.
11 Correct 184 ms 1040 KB Correct.
12 Correct 93 ms 824 KB Correct.
13 Correct 96 ms 864 KB Correct.
14 Correct 184 ms 9756 KB Correct.
15 Correct 192 ms 2900 KB Correct.
16 Correct 91 ms 784 KB Correct.
17 Correct 106 ms 888 KB Correct.
18 Correct 96 ms 812 KB Correct.
19 Correct 218 ms 860 KB Correct.
20 Correct 8 ms 348 KB Correct.
21 Correct 7 ms 604 KB Correct.
22 Correct 14 ms 1628 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 1248 KB Correct.
2 Correct 35 ms 1372 KB Correct.
3 Correct 1103 ms 80840 KB Correct.
4 Correct 248 ms 5132 KB Correct.
5 Correct 873 ms 44216 KB Correct.
6 Correct 382 ms 21188 KB Correct.
7 Correct 398 ms 16552 KB Correct.
8 Correct 299 ms 3044 KB Correct.
9 Correct 186 ms 2192 KB Correct.
10 Correct 168 ms 1980 KB Correct.
11 Correct 217 ms 1620 KB Correct.
12 Correct 203 ms 2244 KB Correct.
13 Correct 217 ms 2436 KB Correct.
14 Correct 996 ms 34592 KB Correct.
15 Correct 909 ms 40780 KB Correct.
16 Correct 355 ms 13816 KB Correct.
17 Correct 288 ms 4932 KB Correct.
18 Correct 192 ms 2496 KB Correct.
19 Correct 236 ms 2340 KB Correct.
20 Correct 208 ms 2288 KB Correct.
21 Correct 494 ms 3412 KB Correct.
22 Correct 17 ms 604 KB Correct.
23 Correct 14 ms 884 KB Correct.
24 Correct 27 ms 2264 KB Correct.