oj.uz

Submission #1107535

# Submission time Handle Problem Language Result Execution time Memory
1107535 2024-11-01T11:59:39 Z yanndev Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 163720 KB 
#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];

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

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

        if (at == H)
            continue;

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

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

    double ans = 1e18;
    for (int i = 0; i <= K; i++)
        ans = min(ans, dist[H][i]);

    if (ans == 1e18)
        ans = -1;
    
    for (int i = 0; i < N; i++)
        adj[i].clear();

    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3152 KB Correct.
2 Correct 14 ms 3152 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 6156 KB Correct.
2 Correct 19 ms 6360 KB Correct.
3 Correct 23 ms 6224 KB Correct.
4 Correct 19 ms 6292 KB Correct.
5 Correct 19 ms 6272 KB Correct.
6 Correct 22 ms 10832 KB Correct.
7 Correct 33 ms 11112 KB Correct.
8 Correct 12 ms 17232 KB Correct.
9 Correct 17 ms 3876 KB Correct.
10 Correct 17 ms 3920 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6264 KB Correct.
2 Correct 20 ms 6224 KB Correct.
3 Correct 19 ms 6248 KB Correct.
4 Correct 23 ms 3920 KB Correct.
5 Correct 19 ms 3792 KB Correct.
6 Correct 8 ms 10064 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 47516 KB Correct.
2 Correct 256 ms 6500 KB Correct.
3 Correct 230 ms 6620 KB Correct.
4 Correct 238 ms 6636 KB Correct.
5 Correct 199 ms 4000 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 6224 KB Correct.
2 Correct 19 ms 6224 KB Correct.
3 Correct 28 ms 6332 KB Correct.
4 Correct 19 ms 11088 KB Correct.
5 Correct 15 ms 3664 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 6224 KB Correct.
2 Correct 20 ms 6224 KB Correct.
3 Correct 37 ms 53064 KB Correct.
4 Correct 14 ms 8540 KB Correct.
5 Correct 23 ms 3892 KB Correct.
6 Correct 18 ms 6300 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 7040 KB Correct.
2 Correct 39 ms 7128 KB Correct.
3 Correct 576 ms 68632 KB Correct.
4 Correct 471 ms 19944 KB Correct.
5 Correct 937 ms 65360 KB Correct.
6 Correct 422 ms 49856 KB Correct.
7 Correct 434 ms 21448 KB Correct.
8 Correct 447 ms 7636 KB Correct.
9 Correct 224 ms 7224 KB Correct.
10 Correct 243 ms 7188 KB Correct.
11 Correct 443 ms 7344 KB Correct.
12 Correct 269 ms 7288 KB Correct.
13 Correct 259 ms 7112 KB Correct.
14 Correct 349 ms 36512 KB Correct.
15 Correct 432 ms 14932 KB Correct.
16 Correct 260 ms 7204 KB Correct.
17 Correct 286 ms 7168 KB Correct.
18 Correct 283 ms 7116 KB Correct.
19 Correct 676 ms 8060 KB Correct.
20 Correct 20 ms 3408 KB Correct.
21 Correct 20 ms 5684 KB Correct.
22 Correct 33 ms 8900 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 950 ms 10028 KB Correct.
2 Correct 125 ms 13552 KB Correct.
3 Correct 554 ms 69232 KB Correct.
4 Correct 994 ms 11284 KB Correct.
5 Execution timed out 3077 ms 163720 KB Time limit exceeded
6 Halted 0 ms 0 KB -