Submission #957557

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
957557	2024-04-04T03:03:55 Z	abczz	Cyberland (APIO23_cyberland)	C++17	100 / 100	1949 ms	140928 KB

cyberland

#include "cyberland.h"
#include <iostream>
#include <vector>
#include <queue>
#include <array>
#define ll long long
#define ld long double

using namespace std;

vector <array<ll, 2>> adj[100000];
ll h;
bool visited[100000];
priority_queue<array<ld, 2>, vector<array<ld, 2>>, greater<array<ld, 2>>> pq[81];
ld dp[100000][81], ep = 1e-9;

void dfs(ll u) {
    visited[u] = 1;
    for (auto [v, x] : adj[u]) {
        if (v != h && !visited[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) {
    K = min(K, 80), h = H;
    for (int i=0; i<N; ++i) {
        visited[i] = 0;
        adj[i].clear();
        for (int j=0; j<=K; ++j) {
            dp[i][j] = 1e18;
        }
    }
    for (int i=0; i<M; ++i) {
        adj[x[i]].push_back({y[i], c[i]});
        adj[y[i]].push_back({x[i], c[i]});
    }
    dfs(0);
    for (int i=0; i<N; ++i) {
        if (visited[i] && (!arr[i] || !i)) {
            dp[i][K] = 0;
            pq[K].push({0, (ld)i});
        }
    }
    for (int i=K; i>=0; --i) {
        while (!pq[i].empty()) {
            auto [w, du] = pq[i].top();
            pq[i].pop();
            ll u = (ll)du;
            if (dp[u][i] != w || u == H) continue;
            for (auto [v, x] : adj[u]) {
                if (dp[v][i]-(w+(ld)x) > ep) {
                    dp[v][i] = w+(ld)x;
                    pq[i].push({dp[v][i], (ld)v});
                }
                if (i && arr[v] == 2 && (dp[v][i-1]-(ld)(w+(ld)x)/2) > ep) {
                    dp[v][i-1] = (w+(ld)x)/2;
                    pq[i-1].push({dp[v][i-1], (ld)v});
                }
            }
        }
    }
    ld f = 1e18;
    for (int i=0; i<=K; ++i) {
        f = min(f, dp[H][i]);
    }
    if (f == 1e18) return -1;
    return f;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	4444 KB	Correct.
2	Correct	22 ms	4444 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	6748 KB	Correct.
2	Correct	33 ms	6748 KB	Correct.
3	Correct	32 ms	6748 KB	Correct.
4	Correct	33 ms	6748 KB	Correct.
5	Correct	33 ms	6748 KB	Correct.
6	Correct	30 ms	17756 KB	Correct.
7	Correct	39 ms	17772 KB	Correct.
8	Correct	22 ms	33112 KB	Correct.
9	Correct	32 ms	4612 KB	Correct.
10	Correct	30 ms	4444 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	6748 KB	Correct.
2	Correct	33 ms	6748 KB	Correct.
3	Correct	31 ms	6748 KB	Correct.
4	Correct	32 ms	4444 KB	Correct.
5	Correct	32 ms	4444 KB	Correct.
6	Correct	9 ms	15708 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	173 ms	88504 KB	Correct.
2	Correct	149 ms	7000 KB	Correct.
3	Correct	132 ms	7248 KB	Correct.
4	Correct	139 ms	7004 KB	Correct.
5	Correct	89 ms	4604 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	6748 KB	Correct.
2	Correct	33 ms	6740 KB	Correct.
3	Correct	32 ms	6748 KB	Correct.
4	Correct	33 ms	18260 KB	Correct.
5	Correct	26 ms	4440 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	6848 KB	Correct.
2	Correct	26 ms	6884 KB	Correct.
3	Correct	75 ms	106664 KB	Correct.
4	Correct	28 ms	16472 KB	Correct.
5	Correct	28 ms	4444 KB	Correct.
6	Correct	28 ms	6820 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	180 ms	7248 KB	Correct.
2	Correct	28 ms	7596 KB	Correct.
3	Correct	762 ms	136096 KB	Correct.
4	Correct	398 ms	36280 KB	Correct.
5	Correct	716 ms	85452 KB	Correct.
6	Correct	296 ms	43848 KB	Correct.
7	Correct	383 ms	38616 KB	Correct.
8	Correct	275 ms	11344 KB	Correct.
9	Correct	146 ms	7324 KB	Correct.
10	Correct	144 ms	7260 KB	Correct.
11	Correct	248 ms	7096 KB	Correct.
12	Correct	158 ms	7252 KB	Correct.
13	Correct	157 ms	7248 KB	Correct.
14	Correct	391 ms	69320 KB	Correct.
15	Correct	333 ms	22708 KB	Correct.
16	Correct	155 ms	7252 KB	Correct.
17	Correct	177 ms	7356 KB	Correct.
18	Correct	175 ms	7552 KB	Correct.
19	Correct	445 ms	7248 KB	Correct.
20	Correct	10 ms	4444 KB	Correct.
21	Correct	13 ms	7004 KB	Correct.
22	Correct	24 ms	9308 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	418 ms	8120 KB	Correct.
2	Correct	63 ms	8784 KB	Correct.
3	Correct	1208 ms	140928 KB	Correct.
4	Correct	421 ms	16724 KB	Correct.
5	Correct	1749 ms	132896 KB	Correct.
6	Correct	727 ms	75016 KB	Correct.
7	Correct	807 ms	65280 KB	Correct.
8	Correct	380 ms	9780 KB	Correct.
9	Correct	331 ms	8924 KB	Correct.
10	Correct	328 ms	9296 KB	Correct.
11	Correct	266 ms	5640 KB	Correct.
12	Correct	369 ms	9040 KB	Correct.
13	Correct	383 ms	9160 KB	Correct.
14	Correct	1949 ms	94088 KB	Correct.
15	Correct	1628 ms	78448 KB	Correct.
16	Correct	663 ms	34652 KB	Correct.
17	Correct	409 ms	13544 KB	Correct.
18	Correct	362 ms	9072 KB	Correct.
19	Correct	408 ms	9024 KB	Correct.
20	Correct	399 ms	9040 KB	Correct.
21	Correct	1093 ms	10080 KB	Correct.
22	Correct	20 ms	4696 KB	Correct.
23	Correct	28 ms	7760 KB	Correct.
24	Correct	54 ms	12372 KB	Correct.

Submission #957557

Compilation message