Submission #749134

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
749134	2023-05-27T11:45:51 Z	Alan	Cyberland (APIO23_cyberland)	C++17	97 / 100	3000 ms	178180 KB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using ld = long double;

struct edge {
    int v;
    ld w;
    int k;
    bool operator< (edge b) const {
        if (k != b.k) return k > b.k;
        return w > b.w;
    }
};
vector<edge> g[100005];
bool vis[100005];
ld di[100005][101];
const ld inf = 1e18;
int h;

void dfs (int u) {
    vis[u] = true;
    if (u == h) return;
    for (auto& [v, w, k] : g[u]) if (!vis[v]) dfs(v);
}

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) {
    h = H;
    K = min(K, 100);
    for (int i = 0; i < N; i++) {
        g[i].clear();
        vis[i] = false;
        for (int j = 0; j <= K; j++) di[i][j] = inf;
    }
    for (int i = 0; i < M; i++) {
        g[x[i]].push_back({y[i], ld(c[i]), 0});
        g[y[i]].push_back({x[i], ld(c[i]), 0});
    }
    dfs(0);
    if (!vis[H]) return -1;
    priority_queue<edge, vector<edge>> pq;
    for (int i = 1; i < N; i++) if (arr[i] == 0 && vis[i]) {
        pq.push({i, 0, 0});
        di[i][0] = 0;
    }
    pq.push({0, 0, 0});
    di[0][0] = 0;
    while (!pq.empty()) {
        auto [u, w, k] = pq.top();
        pq.pop();
        if (u == H) continue;
        if (di[u][k] != w) continue;
        for (auto& [v, vw, vk] : g[u]) if (arr[v] != 0) {
            if (arr[v] == 2 && k+1 <= K && di[v][k+1] > (w+vw)/2) {
                di[v][k+1] = (w+vw)/2;
                pq.push({v, (w+vw)/2, k+1});
            }
            if (di[v][k] > w+vw) {
                di[v][k] = w+vw;
                pq.push({v, w+vw, k});
            }
        }
    }
    ld ans = inf;
    for (int i = 0; i <= K; i++) ans = min(ans, di[H][i]);
    return ans == inf ? -1 : ans;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	2772 KB	Correct.
2	Correct	26 ms	2836 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	4632 KB	Correct.
2	Correct	40 ms	4552 KB	Correct.
3	Correct	36 ms	4588 KB	Correct.
4	Correct	38 ms	4564 KB	Correct.
5	Correct	37 ms	4656 KB	Correct.
6	Correct	42 ms	20092 KB	Correct.
7	Correct	52 ms	19740 KB	Correct.
8	Correct	33 ms	36860 KB	Correct.
9	Correct	33 ms	2900 KB	Correct.
10	Correct	34 ms	2908 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	4560 KB	Correct.
2	Correct	37 ms	4620 KB	Correct.
3	Correct	36 ms	4652 KB	Correct.
4	Correct	35 ms	2900 KB	Correct.
5	Correct	35 ms	2900 KB	Correct.
6	Correct	15 ms	16952 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	153 ms	104316 KB	Correct.
2	Correct	109 ms	4520 KB	Correct.
3	Correct	96 ms	4492 KB	Correct.
4	Correct	99 ms	4408 KB	Correct.
5	Correct	73 ms	2888 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	4856 KB	Correct.
2	Correct	36 ms	4892 KB	Correct.
3	Correct	34 ms	4820 KB	Correct.
4	Correct	45 ms	21504 KB	Correct.
5	Correct	28 ms	2932 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	4872 KB	Correct.
2	Correct	29 ms	4872 KB	Correct.
3	Correct	112 ms	134700 KB	Correct.
4	Correct	32 ms	16132 KB	Correct.
5	Correct	32 ms	2900 KB	Correct.
6	Correct	32 ms	4948 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	113 ms	4904 KB	Correct.
2	Correct	21 ms	6044 KB	Correct.
3	Correct	880 ms	168456 KB	Correct.
4	Correct	420 ms	41276 KB	Correct.
5	Correct	598 ms	76032 KB	Correct.
6	Correct	270 ms	33908 KB	Correct.
7	Correct	400 ms	44584 KB	Correct.
8	Correct	277 ms	8992 KB	Correct.
9	Correct	97 ms	4872 KB	Correct.
10	Correct	89 ms	4932 KB	Correct.
11	Correct	252 ms	5116 KB	Correct.
12	Correct	106 ms	4812 KB	Correct.
13	Correct	109 ms	4992 KB	Correct.
14	Correct	475 ms	84496 KB	Correct.
15	Correct	355 ms	24912 KB	Correct.
16	Correct	100 ms	4840 KB	Correct.
17	Correct	119 ms	4940 KB	Correct.
18	Correct	106 ms	4812 KB	Correct.
19	Correct	242 ms	4812 KB	Correct.
20	Correct	8 ms	2900 KB	Correct.
21	Correct	10 ms	4436 KB	Correct.
22	Correct	19 ms	5844 KB	Correct.

Subtask #8
0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	325 ms	4820 KB	Correct.
2	Correct	52 ms	6040 KB	Correct.
3	Correct	1586 ms	178180 KB	Correct.
4	Correct	468 ms	14456 KB	Correct.
5	Correct	1767 ms	76048 KB	Correct.
6	Correct	734 ms	33912 KB	Correct.
7	Correct	1010 ms	66820 KB	Correct.
8	Correct	445 ms	5488 KB	Correct.
9	Correct	257 ms	4940 KB	Correct.
10	Correct	239 ms	4968 KB	Correct.
11	Correct	333 ms	2920 KB	Correct.
12	Correct	284 ms	4940 KB	Correct.
13	Correct	291 ms	4904 KB	Correct.
14	Execution timed out	3066 ms	77084 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-

Submission #749134

Compilation message