oj.uz

Submission #756522

# Submission time Handle Problem Language Result Execution time Memory
756522 2023-06-11T19:32:33 Z Lobo Cyberland (APIO23_cyberland) C++17
97 / 100
 1275 ms 69324 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;
  	k = min(k,(int) 100);
    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 22 ms 2772 KB Correct.
2 Correct 24 ms 2732 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3204 KB Correct.
2 Correct 27 ms 3156 KB Correct.
3 Correct 27 ms 3104 KB Correct.
4 Correct 27 ms 3132 KB Correct.
5 Correct 27 ms 3148 KB Correct.
6 Correct 27 ms 6400 KB Correct.
7 Correct 32 ms 6304 KB Correct.
8 Correct 18 ms 10068 KB Correct.
9 Correct 25 ms 2764 KB Correct.
10 Correct 31 ms 2760 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3028 KB Correct.
2 Correct 27 ms 3160 KB Correct.
3 Correct 31 ms 3156 KB Correct.
4 Correct 27 ms 2760 KB Correct.
5 Correct 27 ms 2768 KB Correct.
6 Correct 8 ms 5748 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 30732 KB Correct.
2 Correct 339 ms 3668 KB Correct.
3 Correct 297 ms 3860 KB Correct.
4 Correct 285 ms 3704 KB Correct.
5 Correct 228 ms 2868 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3156 KB Correct.
2 Correct 31 ms 3240 KB Correct.
3 Correct 27 ms 3188 KB Correct.
4 Correct 29 ms 6820 KB Correct.
5 Correct 23 ms 2760 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3156 KB Correct.
2 Correct 22 ms 3284 KB Correct.
3 Correct 54 ms 31028 KB Correct.
4 Correct 18 ms 5852 KB Correct.
5 Correct 25 ms 2768 KB Correct.
6 Correct 26 ms 3292 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 4516 KB Correct.
2 Correct 45 ms 5996 KB Correct.
3 Correct 744 ms 41568 KB Correct.
4 Correct 587 ms 12232 KB Correct.
5 Correct 1275 ms 69324 KB Correct.
6 Correct 669 ms 60980 KB Correct.
7 Correct 599 ms 12756 KB Correct.
8 Correct 548 ms 4404 KB Correct.
9 Correct 291 ms 5464 KB Correct.
10 Correct 306 ms 4648 KB Correct.
11 Correct 563 ms 3604 KB Correct.
12 Correct 311 ms 4756 KB Correct.
13 Correct 338 ms 4704 KB Correct.
14 Correct 560 ms 22940 KB Correct.
15 Correct 558 ms 8708 KB Correct.
16 Correct 307 ms 4612 KB Correct.
17 Correct 373 ms 4476 KB Correct.
18 Correct 347 ms 4520 KB Correct.
19 Correct 865 ms 4540 KB Correct.
20 Correct 26 ms 3204 KB Correct.
21 Correct 26 ms 3828 KB Correct.
22 Correct 42 ms 6732 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 1095 ms 7936 KB Wrong Answer.
2 Halted 0 ms 0 KB -