Submission #1065350

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1065350	2024-08-19T06:31:46 Z	stdfloat	Cyberland (APIO23_cyberland)	C++17	97 / 100	3000 ms	94584 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]) {
            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	604 KB	Correct.
2	Correct	15 ms	600 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	860 KB	Correct.
2	Correct	25 ms	900 KB	Correct.
3	Correct	38 ms	872 KB	Correct.
4	Correct	30 ms	860 KB	Correct.
5	Correct	25 ms	856 KB	Correct.
6	Correct	23 ms	4580 KB	Correct.
7	Correct	30 ms	4556 KB	Correct.
8	Correct	14 ms	8796 KB	Correct.
9	Correct	31 ms	348 KB	Correct.
10	Correct	24 ms	344 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	856 KB	Correct.
2	Correct	24 ms	792 KB	Correct.
3	Correct	23 ms	860 KB	Correct.
4	Correct	25 ms	344 KB	Correct.
5	Correct	25 ms	580 KB	Correct.
6	Correct	6 ms	3672 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	152 ms	26556 KB	Correct.
2	Correct	189 ms	1028 KB	Correct.
3	Correct	163 ms	1012 KB	Correct.
4	Correct	166 ms	1048 KB	Correct.
5	Correct	152 ms	604 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	848 KB	Correct.
2	Correct	21 ms	856 KB	Correct.
3	Correct	20 ms	840 KB	Correct.
4	Correct	21 ms	4188 KB	Correct.
5	Correct	18 ms	564 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	860 KB	Correct.
2	Correct	19 ms	864 KB	Correct.
3	Correct	28 ms	7256 KB	Correct.
4	Correct	14 ms	2744 KB	Correct.
5	Correct	22 ms	576 KB	Correct.
6	Correct	20 ms	796 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	165 ms	1180 KB	Correct.
2	Correct	25 ms	1692 KB	Correct.
3	Correct	572 ms	33908 KB	Correct.
4	Correct	473 ms	8996 KB	Correct.
5	Correct	629 ms	50668 KB	Correct.
6	Correct	304 ms	24992 KB	Correct.
7	Correct	466 ms	8896 KB	Correct.
8	Correct	456 ms	3248 KB	Correct.
9	Correct	156 ms	1492 KB	Correct.
10	Correct	141 ms	2256 KB	Correct.
11	Correct	437 ms	2188 KB	Correct.
12	Correct	161 ms	2184 KB	Correct.
13	Correct	178 ms	2500 KB	Correct.
14	Correct	396 ms	13488 KB	Correct.
15	Correct	446 ms	4860 KB	Correct.
16	Correct	144 ms	2080 KB	Correct.
17	Correct	184 ms	1968 KB	Correct.
18	Correct	177 ms	1960 KB	Correct.
19	Correct	388 ms	2532 KB	Correct.
20	Correct	13 ms	600 KB	Correct.
21	Correct	11 ms	900 KB	Correct.
22	Correct	25 ms	3388 KB	Correct.

Subtask #8
0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	552 ms	3500 KB	Correct.
2	Correct	78 ms	4668 KB	Correct.
3	Correct	494 ms	71508 KB	Correct.
4	Correct	963 ms	6148 KB	Correct.
5	Correct	2215 ms	94584 KB	Correct.
6	Correct	1149 ms	78716 KB	Correct.
7	Correct	1077 ms	25336 KB	Correct.
8	Correct	1151 ms	3732 KB	Correct.
9	Correct	515 ms	4952 KB	Correct.
10	Correct	499 ms	4832 KB	Correct.
11	Execution timed out	3028 ms	1524 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Submission #1065350

Compilation message