oj.uz

Submission #919557

# Submission time Handle Problem Language Result Execution time Memory
919557 2024-02-01T06:29:30 Z dosts Cyberland (APIO23_cyberland) C++17
100 / 100
 1712 ms 67240 KB 
#pragma GCC optimize("O3,unroll-loops")
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
 
vector<pair<int,int>> edges[100000];
 
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,68);
    for (int i=0;i<N;i++) edges[i].clear();
    for (int i=0;i<M;i++) {
        edges[x[i]].push_back({y[i],c[i]});
        edges[y[i]].push_back({x[i],c[i]});
    }
    int ARR[arr.size()];
    for (int i=0;i<arr.size();i++) ARR[i] = arr[i];
    double dp[N][K+1];
    for (int i=0;i<N;i++) {
        for (int j=0;j<=K;j++) dp[i][j] = 2e18;
    }
    dp[0][0] = 0;
    for (int used=0;used<=K;used++) {
        priority_queue<pair<double,int>,vector<pair<double,int>>,greater<pair<double,int>>> pq;
        if (used) for (int i=0;i<N;i++) dp[i][used] = min(dp[i][used],dp[i][used-1]);
        for (int i=0;i<N;i++) if (dp[i][used] != 2e18) pq.push({dp[i][used],i});
        while (!pq.empty()) {
            pair<double,int> f = pq.top();
            pq.pop();
            double cost = f.first;
            int city = f.second;
            if (dp[city][used] < cost) continue;
            if (city == H) continue;
            for (auto it : edges[city]) {
                int dest = it.first;
                int go = it.second; 
                if (!ARR[dest]) {
                    if (dp[dest][used]>0) {
                        pq.push({0,dest});
                        dp[dest][used] = 0;
                    }
                }
                else {
                    if (dp[dest][used] > cost+go) {
                        pq.push({cost+go,dest}); 
                        dp[dest][used] = cost+go;
                    }               
                    if (ARR[dest] == 2) {
                        if (used!=K && dp[dest][used+1] > (cost+go)/2) {
                            dp[dest][used+1] = (cost+go)/2;
                        }
                    }
                }
            }
        }
    }
    return dp[H][K]==2e18?-1:dp[H][K];
}

Compilation message

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:16:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for (int i=0;i<arr.size();i++) ARR[i] = arr[i];
      |                  ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2896 KB Correct.
2 Correct 31 ms 2904 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 3140 KB Correct.
2 Correct 135 ms 3432 KB Correct.
3 Correct 131 ms 3180 KB Correct.
4 Correct 143 ms 3588 KB Correct.
5 Correct 134 ms 3192 KB Correct.
6 Correct 190 ms 6364 KB Correct.
7 Correct 259 ms 6428 KB Correct.
8 Correct 121 ms 9820 KB Correct.
9 Correct 67 ms 2648 KB Correct.
10 Correct 64 ms 2856 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 3140 KB Correct.
2 Correct 130 ms 3648 KB Correct.
3 Correct 114 ms 3408 KB Correct.
4 Correct 71 ms 2852 KB Correct.
5 Correct 71 ms 2648 KB Correct.
6 Correct 43 ms 5592 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 21260 KB Correct.
2 Correct 92 ms 3152 KB Correct.
3 Correct 78 ms 3152 KB Correct.
4 Correct 86 ms 3152 KB Correct.
5 Correct 53 ms 2648 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 3160 KB Correct.
2 Correct 57 ms 3160 KB Correct.
3 Correct 64 ms 3188 KB Correct.
4 Correct 102 ms 6088 KB Correct.
5 Correct 46 ms 2648 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 3204 KB Correct.
2 Correct 53 ms 3232 KB Correct.
3 Correct 61 ms 26452 KB Correct.
4 Correct 65 ms 5368 KB Correct.
5 Correct 45 ms 2860 KB Correct.
6 Correct 62 ms 3208 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 3152 KB Correct.
2 Correct 13 ms 3416 KB Correct.
3 Correct 937 ms 26672 KB Correct.
4 Correct 409 ms 9064 KB Correct.
5 Correct 367 ms 17740 KB Correct.
6 Correct 128 ms 9656 KB Correct.
7 Correct 389 ms 8984 KB Correct.
8 Correct 292 ms 3920 KB Correct.
9 Correct 72 ms 3160 KB Correct.
10 Correct 71 ms 3160 KB Correct.
11 Correct 237 ms 3368 KB Correct.
12 Correct 80 ms 3176 KB Correct.
13 Correct 77 ms 3216 KB Correct.
14 Correct 309 ms 10448 KB Correct.
15 Correct 326 ms 5524 KB Correct.
16 Correct 72 ms 3152 KB Correct.
17 Correct 94 ms 3160 KB Correct.
18 Correct 84 ms 3160 KB Correct.
19 Correct 305 ms 3156 KB Correct.
20 Correct 6 ms 2648 KB Correct.
21 Correct 7 ms 2908 KB Correct.
22 Correct 11 ms 3416 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 3408 KB Correct.
2 Correct 24 ms 3672 KB Correct.
3 Correct 1712 ms 67240 KB Correct.
4 Correct 416 ms 5652 KB Correct.
5 Correct 756 ms 28500 KB Correct.
6 Correct 256 ms 12704 KB Correct.
7 Correct 535 ms 17004 KB Correct.
8 Correct 333 ms 3836 KB Correct.
9 Correct 131 ms 3664 KB Correct.
10 Correct 122 ms 3416 KB Correct.
11 Correct 166 ms 2896 KB Correct.
12 Correct 142 ms 3500 KB Correct.
13 Correct 130 ms 3416 KB Correct.
14 Correct 1201 ms 29200 KB Correct.
15 Correct 1482 ms 34868 KB Correct.
16 Correct 663 ms 14168 KB Correct.
17 Correct 402 ms 5180 KB Correct.
18 Correct 123 ms 3408 KB Correct.
19 Correct 161 ms 3540 KB Correct.
20 Correct 158 ms 3924 KB Correct.
21 Correct 591 ms 3420 KB Correct.
22 Correct 8 ms 2648 KB Correct.
23 Correct 11 ms 3160 KB Correct.
24 Correct 20 ms 3672 KB Correct.