Submission #1065349

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1065349	2024-08-19T06:31:18 Z	stdfloat	Cyberland (APIO23_cyberland)	C++17	97 / 100	3000 ms	95320 KB

cyberland

#include <bits/stdc++.h>
#include "cyberland.h"
using namespace std;
 
#define ff  first
#define ss  second
#define pii pair<int, int>
 
double solve(int n, int M, int K, int H, vector<int> X, vector<int> Y, vector<int> C, vector<int> a) {
    vector<vector<pii>> E(n);
    for (int i = 0; i < M; i++) {
        E[X[i]].push_back({Y[i], C[i]});
        E[Y[i]].push_back({X[i], C[i]});
    }
 
    queue<int> q;
    vector<bool> vis0(n);
    q.push(0); vis0[0] = true;
    while (!q.empty()) {
        int x = q.front(); q.pop();
 
        if (x == H) continue;
 
        for (auto [i, w] : E[x]) {
            if (!vis0[i]) {
                q.push(i);
                vis0[i] = true;
            }
        }
    }
 
    if (!vis0[H]) return -1;
 
    K = min(K, 66);

    vector<vector<pii>> G(n);
    for (int i = 0; i < n; i++) {
        for (auto j : E[i]) {
            if (a[j.ff]) G[i].push_back(j);
        }
    }
    E = G;
 
    vector<vector<double>> dis(n, vector<double>(K + 1, 1e18));
    priority_queue<pair<double, int>> pq;
    for (int i = 0; i < n; i++) {
        if (!i || (!a[i] && vis0[i])) {
            dis[i][0] = 0;
            pq.push({0, 70 * i});
        }
    }
    while (!pq.empty()) {
        auto [d, x] = pq.top(); d = -d; pq.pop();
        int y = x % 70; x /= 70;
    
        if (d != dis[x][y]) continue;
 
        if (x == H) continue;
    
        for (auto [i, w] : E[x]) {
            assert(a[i]);
 
            if (d + w < dis[i][y]) {
                dis[i][y] = d + w;
                pq.push({-dis[i][y], y + 70 * i});
            }
            if (a[i] == 2 && y < K && (d + w) / 2 < dis[i][y + 1]) {
                dis[i][y + 1] = (d + w) / 2;
                pq.push({-dis[i][y + 1], y + 1 + 70 * i});
            }
        }
    }
 
    return *min_element(dis[H].begin(), dis[H].end());
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	860 KB	Correct.
2	Correct	15 ms	856 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	1628 KB	Correct.
2	Correct	26 ms	1872 KB	Correct.
3	Correct	24 ms	1884 KB	Correct.
4	Correct	26 ms	1872 KB	Correct.
5	Correct	32 ms	1752 KB	Correct.
6	Correct	23 ms	5560 KB	Correct.
7	Correct	32 ms	5320 KB	Correct.
8	Correct	17 ms	9304 KB	Correct.
9	Correct	25 ms	1328 KB	Correct.
10	Correct	24 ms	1372 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	1692 KB	Correct.
2	Correct	26 ms	1816 KB	Correct.
3	Correct	23 ms	1820 KB	Correct.
4	Correct	35 ms	1404 KB	Correct.
5	Correct	25 ms	1372 KB	Correct.
6	Correct	7 ms	4004 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	157 ms	27828 KB	Correct.
2	Correct	199 ms	1920 KB	Correct.
3	Correct	163 ms	2040 KB	Correct.
4	Correct	169 ms	1884 KB	Correct.
5	Correct	160 ms	1500 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	1688 KB	Correct.
2	Correct	28 ms	1756 KB	Correct.
3	Correct	23 ms	1724 KB	Correct.
4	Correct	22 ms	4956 KB	Correct.
5	Correct	19 ms	1372 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	1880 KB	Correct.
2	Correct	21 ms	1740 KB	Correct.
3	Correct	27 ms	9040 KB	Correct.
4	Correct	17 ms	3452 KB	Correct.
5	Correct	20 ms	1372 KB	Correct.
6	Correct	20 ms	1740 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	168 ms	2032 KB	Correct.
2	Correct	25 ms	1792 KB	Correct.
3	Correct	573 ms	36324 KB	Correct.
4	Correct	465 ms	11104 KB	Correct.
5	Correct	643 ms	52376 KB	Correct.
6	Correct	324 ms	26556 KB	Correct.
7	Correct	458 ms	10076 KB	Correct.
8	Correct	448 ms	3268 KB	Correct.
9	Correct	157 ms	1344 KB	Correct.
10	Correct	142 ms	2268 KB	Correct.
11	Correct	440 ms	2740 KB	Correct.
12	Correct	167 ms	2356 KB	Correct.
13	Correct	176 ms	2460 KB	Correct.
14	Correct	388 ms	13792 KB	Correct.
15	Correct	446 ms	5612 KB	Correct.
16	Correct	154 ms	2264 KB	Correct.
17	Correct	191 ms	2156 KB	Correct.
18	Correct	170 ms	2120 KB	Correct.
19	Correct	379 ms	3256 KB	Correct.
20	Correct	12 ms	600 KB	Correct.
21	Correct	11 ms	980 KB	Correct.
22	Correct	26 ms	3536 KB	Correct.

Subtask #8
0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	546 ms	3704 KB	Correct.
2	Correct	77 ms	4668 KB	Correct.
3	Correct	470 ms	72664 KB	Correct.
4	Correct	973 ms	6648 KB	Correct.
5	Correct	2199 ms	95320 KB	Correct.
6	Correct	1146 ms	78832 KB	Correct.
7	Correct	1080 ms	25344 KB	Correct.
8	Correct	1137 ms	3880 KB	Correct.
9	Correct	509 ms	4912 KB	Correct.
10	Correct	486 ms	4888 KB	Correct.
11	Execution timed out	3036 ms	1532 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Submission #1065349

Compilation message