oj.uz

Submission #818974

# Submission time Handle Problem Language Result Execution time Memory
818974 2023-08-10T07:30:02 Z 12345678 Cyberland (APIO23_cyberland) C++17
100 / 100
 187 ms 80448 KB 
#include "cyberland.h"
 
#include <bits/stdc++.h>
 
using namespace std;
 
#define node tuple<double, int, int>
 
const int nx=1e5+5, kx=70;
double p[kx+2];
bool can[nx];
 
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, 70);
    priority_queue<node, vector<node>, greater<node>> pq;
    vector<vector<pair<int, double>>> d(N+2);
    vector<vector<double>> dp(N, vector<double>(K+2, DBL_MAX));
    vector<vector<bool>> vs(N, vector<bool>(K+2, 0));
    queue<int> q;
    for (int i=0; i<N; i++) can[i]=0;
    for (int i=0; i<M; i++) 
    {
        d[x[i]].emplace_back(y[i], c[i]);
        d[y[i]].emplace_back(x[i], c[i]);
    }
    q.emplace(0);
    can[H]=1;
    while (!q.empty())
    {
        int x=q.front();
        q.pop();
        if (can[x]) continue;
        can[x]=1;
        for (auto [y, z]:d[x]) if (!can[y]) q.push(y);
    }
    p[0]=1;
    for (int i=1; i<=K; i++) p[i]=p[i-1]/2;
    dp[H][0]=0; arr[0]=0;
    pq.emplace(0, H, 0);
    while (!pq.empty())
    {
        auto [cw, cl, ck]=pq.top();
        pq.pop();
        if (vs[cl][ck]) continue;
        vs[cl][ck]=1;
        if (arr[cl]==0&&can[cl]) return cw;
        for (auto [v, w]:d[cl])
        {
            if (!can[v]||v==H) continue;
            double nw=cw+w*p[ck];
            if (nw<dp[v][ck]) dp[v][ck]=nw, pq.emplace(nw, v, ck);
            if (arr[v]==2&&ck<K&&nw<dp[v][ck+1]) dp[v][ck+1]=nw, pq.emplace(nw, v, ck+1); 
        }
    }
    return -1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 724 KB Correct.
2 Correct 19 ms 728 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1652 KB Correct.
2 Correct 28 ms 1864 KB Correct.
3 Correct 28 ms 1748 KB Correct.
4 Correct 31 ms 1808 KB Correct.
5 Correct 28 ms 1856 KB Correct.
6 Correct 22 ms 5732 KB Correct.
7 Correct 31 ms 5572 KB Correct.
8 Correct 15 ms 9812 KB Correct.
9 Correct 32 ms 1292 KB Correct.
10 Correct 28 ms 1228 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1780 KB Correct.
2 Correct 37 ms 1684 KB Correct.
3 Correct 27 ms 1708 KB Correct.
4 Correct 29 ms 1300 KB Correct.
5 Correct 28 ms 1284 KB Correct.
6 Correct 6 ms 4164 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 28600 KB Correct.
2 Correct 27 ms 1812 KB Correct.
3 Correct 24 ms 1800 KB Correct.
4 Correct 30 ms 1772 KB Correct.
5 Correct 30 ms 1312 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1676 KB Correct.
2 Correct 35 ms 1768 KB Correct.
3 Correct 31 ms 1772 KB Correct.
4 Correct 29 ms 5308 KB Correct.
5 Correct 29 ms 1164 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1768 KB Correct.
2 Correct 24 ms 1664 KB Correct.
3 Correct 61 ms 37736 KB Correct.
4 Correct 22 ms 3648 KB Correct.
5 Correct 30 ms 1308 KB Correct.
6 Correct 27 ms 1672 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1672 KB Correct.
2 Correct 5 ms 1216 KB Correct.
3 Correct 70 ms 36708 KB Correct.
4 Correct 54 ms 10872 KB Correct.
5 Correct 45 ms 22120 KB Correct.
6 Correct 36 ms 11716 KB Correct.
7 Correct 61 ms 10388 KB Correct.
8 Correct 54 ms 3348 KB Correct.
9 Correct 30 ms 1696 KB Correct.
10 Correct 25 ms 1676 KB Correct.
11 Correct 63 ms 2688 KB Correct.
12 Correct 32 ms 1816 KB Correct.
13 Correct 27 ms 1748 KB Correct.
14 Correct 52 ms 14768 KB Correct.
15 Correct 55 ms 5452 KB Correct.
16 Correct 29 ms 1732 KB Correct.
17 Correct 29 ms 1868 KB Correct.
18 Correct 29 ms 1804 KB Correct.
19 Correct 56 ms 2692 KB Correct.
20 Correct 4 ms 468 KB Correct.
21 Correct 3 ms 724 KB Correct.
22 Correct 4 ms 1460 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2076 KB Correct.
2 Correct 4 ms 1748 KB Correct.
3 Correct 113 ms 80448 KB Correct.
4 Correct 58 ms 5128 KB Correct.
5 Correct 51 ms 33304 KB Correct.
6 Correct 32 ms 14900 KB Correct.
7 Correct 61 ms 15468 KB Correct.
8 Correct 61 ms 3164 KB Correct.
9 Correct 30 ms 1976 KB Correct.
10 Correct 25 ms 1980 KB Correct.
11 Correct 187 ms 1608 KB Correct.
12 Correct 30 ms 2132 KB Correct.
13 Correct 30 ms 2112 KB Correct.
14 Correct 65 ms 33420 KB Correct.
15 Correct 69 ms 40660 KB Correct.
16 Correct 52 ms 14584 KB Correct.
17 Correct 65 ms 4968 KB Correct.
18 Correct 39 ms 2128 KB Correct.
19 Correct 28 ms 2112 KB Correct.
20 Correct 39 ms 2116 KB Correct.
21 Correct 53 ms 3024 KB Correct.
22 Correct 4 ms 468 KB Correct.
23 Correct 3 ms 980 KB Correct.
24 Correct 4 ms 1748 KB Correct.