Submission #1107540

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1107540	2024-11-01T12:22:53 Z	yanndev	Cyberland (APIO23_cyberland)	C++17	100 / 100	115 ms	66436 KB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std;

vector<pair<int, int>> adj[100042];
bool vis[100042];
double dist[100042][71];
double pows[128];

void initDfs(int node, int H) {
    vis[node] = true;
    for (auto& x: adj[node])
        if (x.fi != H && !vis[x.fi])
            initDfs(x.fi, H);
}

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    K = min(K, 70);
    
    for (int i = 0; i < N; i++)
        adj[i].clear();

    
    pows[0] = 1;
    for (int i = 1; i <= K + 1; i++)
        pows[i] = pows[i - 1] / (double)2;

    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]});
    }

    for (int i = 0; i < N; i++)
        for (int j = 0; j <= K; j++)
            dist[i][j] = 1e18;

    for (int i = 0; i < N; i++)
        vis[i] = false;
        
    initDfs(0, H);

    priority_queue<tuple<double, int, int>> nxt {};

    arr[0] = 0;
    /*for (int i = 0; i < N; i++) {
        if (vis[i] && arr[i] == 0) {
            dist[i][0] = 0;
            nxt.push({0, 0, i});
        }
    }*/
    
    nxt.push({0, 0, H});
    dist[H][0] = 0;

    while (!nxt.empty()) {
        auto [dst, op2, at] = nxt.top();
        nxt.pop();
        dst *= -1;

        if (arr[at] == 0)
            return dst;

        if (dist[at][op2] == dst) {
            for (auto& x: adj[at]) {
                // no divide
                if (!vis[x.fi])
                    continue;
                
                double nxtDst = dst + (double)x.se * pows[op2];
                if (nxtDst < dist[x.fi][op2]) {
                    dist[x.fi][op2] = nxtDst;
                    nxt.push(make_tuple(-nxtDst, op2, x.fi));
                }

                // use divide
                nxtDst = dst + (double)x.se * pows[op2 + 1];
                if (arr[at] == 2 && op2 < K && nxtDst < dist[x.fi][op2 + 1]) {
                    dist[x.fi][op2 + 1] = nxtDst;
                    nxt.push(make_tuple(-nxtDst, op2 + 1, x.fi));   
                }
            }
        }
    }
    
    return -1;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	2896 KB	Correct.
2	Correct	15 ms	3004 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	5368 KB	Correct.
2	Correct	22 ms	5368 KB	Correct.
3	Correct	14 ms	5368 KB	Correct.
4	Correct	17 ms	5200 KB	Correct.
5	Correct	16 ms	5252 KB	Correct.
6	Correct	19 ms	10576 KB	Correct.
7	Correct	18 ms	9812 KB	Correct.
8	Correct	13 ms	16720 KB	Correct.
9	Correct	16 ms	2896 KB	Correct.
10	Correct	15 ms	2896 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	5200 KB	Correct.
2	Correct	17 ms	5268 KB	Correct.
3	Correct	14 ms	5368 KB	Correct.
4	Correct	16 ms	2896 KB	Correct.
5	Correct	16 ms	3040 KB	Correct.
6	Correct	6 ms	9808 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	39752 KB	Correct.
2	Correct	16 ms	5200 KB	Correct.
3	Correct	15 ms	5368 KB	Correct.
4	Correct	13 ms	5264 KB	Correct.
5	Correct	15 ms	2896 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	5368 KB	Correct.
2	Correct	16 ms	5368 KB	Correct.
3	Correct	18 ms	5372 KB	Correct.
4	Correct	17 ms	10064 KB	Correct.
5	Correct	13 ms	2896 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	5200 KB	Correct.
2	Correct	13 ms	5200 KB	Correct.
3	Correct	34 ms	51336 KB	Correct.
4	Correct	11 ms	8272 KB	Correct.
5	Correct	14 ms	2896 KB	Correct.
6	Correct	14 ms	5200 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	5200 KB	Correct.
2	Correct	3 ms	5200 KB	Correct.
3	Correct	48 ms	62928 KB	Correct.
4	Correct	29 ms	16956 KB	Correct.
5	Correct	32 ms	28496 KB	Correct.
6	Correct	22 ms	14160 KB	Correct.
7	Correct	29 ms	19148 KB	Correct.
8	Correct	28 ms	5340 KB	Correct.
9	Correct	14 ms	5200 KB	Correct.
10	Correct	13 ms	5200 KB	Correct.
11	Correct	29 ms	6676 KB	Correct.
12	Correct	14 ms	5200 KB	Correct.
13	Correct	14 ms	5200 KB	Correct.
14	Correct	34 ms	33152 KB	Correct.
15	Correct	28 ms	12244 KB	Correct.
16	Correct	16 ms	5968 KB	Correct.
17	Correct	15 ms	5200 KB	Correct.
18	Correct	17 ms	5968 KB	Correct.
19	Correct	27 ms	5200 KB	Correct.
20	Correct	3 ms	2896 KB	Correct.
21	Correct	3 ms	5200 KB	Correct.
22	Correct	5 ms	5456 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	5200 KB	Correct.
2	Correct	4 ms	5200 KB	Correct.
3	Correct	64 ms	66436 KB	Correct.
4	Correct	29 ms	7732 KB	Correct.
5	Correct	33 ms	28488 KB	Correct.
6	Correct	23 ms	14684 KB	Correct.
7	Correct	37 ms	28856 KB	Correct.
8	Correct	30 ms	7248 KB	Correct.
9	Correct	25 ms	6224 KB	Correct.
10	Correct	16 ms	6224 KB	Correct.
11	Correct	115 ms	4168 KB	Correct.
12	Correct	17 ms	6356 KB	Correct.
13	Correct	18 ms	6224 KB	Correct.
14	Correct	39 ms	31876 KB	Correct.
15	Correct	44 ms	37288 KB	Correct.
16	Correct	47 ms	16736 KB	Correct.
17	Correct	32 ms	7248 KB	Correct.
18	Correct	18 ms	6240 KB	Correct.
19	Correct	18 ms	6224 KB	Correct.
20	Correct	17 ms	6240 KB	Correct.
21	Correct	32 ms	7248 KB	Correct.
22	Correct	3 ms	2896 KB	Correct.
23	Correct	3 ms	5200 KB	Correct.
24	Correct	4 ms	5712 KB	Correct.

Submission #1107540

Compilation message