oj.uz

Submission #756520

# Submission time Handle Problem Language Result Execution time Memory
756520 2023-06-11T19:31:38 Z Lobo Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 69232 KB 
#include "cyberland.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()

const int maxn = 1e5+10;
const int inf = 1e18+10;

int n, m, k, a[maxn], h, mark[maxn];
vector<pair<int,int>> g[maxn];
double d[maxn][35];

void dfs(int u) {
    mark[u] = 1;
    if(u == h) return;
    for(auto v : g[u]) {
        if(mark[v.fr] == 0) dfs(v.fr);
    }
}


double solve(int32_t N, int32_t M, int32_t K, int32_t H, std::vector<int32_t> x, std::vector<int32_t> y, std::vector<int32_t> c, std::vector<int32_t> arr) {

    n = N;
    m = M;
    k = K;
    h = H;
    for(int i = 0; i < n; i++) {
        g[i].clear();
        mark[i] = 0;
        a[i] = arr[i];
    }
    for(int i = 0; i < m; i++) {
        g[x[i]].pb(mp(y[i],c[i]));
        g[y[i]].pb(mp(x[i],c[i]));
    }

    dfs(0);

    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= k; j++) {
            d[i][j] = inf;
        }
    }
    priority_queue<pair<double,pair<int,int>>> pq;
    d[0][0] = 0;
    pq.push(mp(0,mp(0,0)));
    for(int i = 1; i < n; i++) {
        if(a[i] == 0 && mark[i]) {
            d[i][0] = 0;
            pq.push(mp(0,mp(i,0)));
        }
    }
    while(pq.size()) {
        int u = pq.top().sc.fr;
        int j = pq.top().sc.sc;
        double dist = -pq.top().fr;
        pq.pop();
        if(d[u][j] != dist) continue;
        if(u == h) continue;

        for(auto V : g[u]) {
            int v = V.fr;
            int w = V.sc;
            if(d[v][j] > d[u][j]+w) {
                d[v][j] = d[u][j]+w;
                pq.push(mp(-d[v][j],mp(v,j)));
            }
            if(a[v] == 2 && j != k && d[v][j+1] > (d[u][j]+w)/((double) 2.0)) {
                d[v][j+1] = (d[u][j]+w)/((double)2.0);
                pq.push(mp(-d[v][j+1],mp(v,j+1)));
            }
        }
    }
    double ans = inf;
    for(int i = 0; i <= k; i++) {
        ans = min(ans, d[h][i]);
    }
    if(ans == inf) return -1;
    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2772 KB Correct.
2 Correct 24 ms 2772 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3176 KB Correct.
2 Correct 27 ms 3144 KB Correct.
3 Correct 36 ms 3148 KB Correct.
4 Correct 30 ms 3120 KB Correct.
5 Correct 28 ms 3156 KB Correct.
6 Correct 28 ms 6428 KB Correct.
7 Correct 33 ms 6332 KB Correct.
8 Correct 17 ms 10068 KB Correct.
9 Correct 25 ms 2644 KB Correct.
10 Correct 24 ms 2896 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3128 KB Correct.
2 Correct 27 ms 3156 KB Correct.
3 Correct 28 ms 3156 KB Correct.
4 Correct 29 ms 2768 KB Correct.
5 Correct 30 ms 2768 KB Correct.
6 Correct 9 ms 5864 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 30740 KB Correct.
2 Correct 329 ms 3740 KB Correct.
3 Correct 292 ms 3712 KB Correct.
4 Correct 282 ms 3676 KB Correct.
5 Correct 242 ms 2828 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3272 KB Correct.
2 Correct 28 ms 3156 KB Correct.
3 Correct 27 ms 3220 KB Correct.
4 Correct 27 ms 6868 KB Correct.
5 Correct 22 ms 2764 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3284 KB Correct.
2 Correct 25 ms 3248 KB Correct.
3 Correct 60 ms 31036 KB Correct.
4 Correct 20 ms 5844 KB Correct.
5 Correct 24 ms 2752 KB Correct.
6 Correct 27 ms 3240 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 4572 KB Correct.
2 Correct 62 ms 5928 KB Correct.
3 Correct 800 ms 41480 KB Correct.
4 Correct 586 ms 12236 KB Correct.
5 Correct 1362 ms 69232 KB Correct.
6 Correct 651 ms 61016 KB Correct.
7 Correct 583 ms 12736 KB Correct.
8 Correct 589 ms 4548 KB Correct.
9 Correct 284 ms 5404 KB Correct.
10 Correct 317 ms 4764 KB Correct.
11 Correct 559 ms 3708 KB Correct.
12 Correct 319 ms 4716 KB Correct.
13 Correct 314 ms 4568 KB Correct.
14 Correct 576 ms 23060 KB Correct.
15 Correct 596 ms 8668 KB Correct.
16 Correct 321 ms 4672 KB Correct.
17 Correct 368 ms 4532 KB Correct.
18 Correct 376 ms 4456 KB Correct.
19 Correct 889 ms 4528 KB Correct.
20 Correct 24 ms 3232 KB Correct.
21 Correct 27 ms 3780 KB Correct.
22 Correct 47 ms 6732 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3088 ms 20032 KB Time limit exceeded
2 Halted 0 ms 0 KB -