oj.uz

Submission #865336

# Submission time Handle Problem Language Result Execution time Memory
865336 2023-10-24T07:32:27 Z jk410 Cyberland (APIO23_cyberland) C++17
100 / 100
 362 ms 20280 KB 
#include "cyberland.h"
#include <vector>
#include <queue>
#include <functional>
using namespace std;
struct edge{
    int v;
    double cost;
    bool operator<(const edge &tmp)const{
        return cost>tmp.cost;
    }
};
const int MAXK=100;
const double INF=1e15;
vector<edge> Adj[100000];
bool Ikeru[100000];
double Dist[100000];
priority_queue<edge> PQ;
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){
    for (int i=0; i<N; i++)
        Adj[i].clear();
    fill(Ikeru,Ikeru+N,false);
    fill(Dist,Dist+N,INF);
    while (!PQ.empty())
        PQ.pop();
    for (int i=0; i<M; i++){
        Adj[x[i]].push_back({y[i],(double)c[i]});
        Adj[y[i]].push_back({x[i],(double)c[i]});
    }
    function<void(int)> dfs=[&](int v){
        Ikeru[v]=true;
        if (v==H)
            return;
        for (edge i:Adj[v]){
            if (!Ikeru[i.v])
                dfs(i.v);
        }
    };
    dfs(0);
    if (!Ikeru[H])
        return -1;
    K=min(K,MAXK)+1;
    for (int i=0; i<N; i++){
        if (Ikeru[i]&&!arr[i]){
            Dist[i]=0;
            PQ.push({i,0});
        }
    }
    Dist[0]=0;
    PQ.push({0,0});
    while (K--){
        while (!PQ.empty()){
            edge cur=PQ.top();
            PQ.pop();
            if (Dist[cur.v]<cur.cost||cur.v==H)
                continue;
            for (edge i:Adj[cur.v]){
                if (Dist[i.v]>cur.cost+i.cost){
                    Dist[i.v]=cur.cost+i.cost;
                    PQ.push({i.v,Dist[i.v]});
                }
            }
        }
        for (int i=0; i<N; i++){
            if (Ikeru[i]&&arr[i]==2){
                PQ.push({i,Dist[i]/2});
                Dist[i]=INF;
            }
        }
    }
    return Dist[H];
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3868 KB Correct.
2 Correct 17 ms 3932 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 4444 KB Correct.
2 Correct 22 ms 4700 KB Correct.
3 Correct 21 ms 4444 KB Correct.
4 Correct 22 ms 4700 KB Correct.
5 Correct 22 ms 4680 KB Correct.
6 Correct 19 ms 5212 KB Correct.
7 Correct 24 ms 5468 KB Correct.
8 Correct 11 ms 5720 KB Correct.
9 Correct 21 ms 4444 KB Correct.
10 Correct 24 ms 4424 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4432 KB Correct.
2 Correct 22 ms 4500 KB Correct.
3 Correct 20 ms 4444 KB Correct.
4 Correct 22 ms 4316 KB Correct.
5 Correct 22 ms 4444 KB Correct.
6 Correct 5 ms 4440 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 10712 KB Correct.
2 Correct 47 ms 4912 KB Correct.
3 Correct 42 ms 4544 KB Correct.
4 Correct 44 ms 4656 KB Correct.
5 Correct 36 ms 4432 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4500 KB Correct.
2 Correct 20 ms 4732 KB Correct.
3 Correct 20 ms 4692 KB Correct.
4 Correct 21 ms 5976 KB Correct.
5 Correct 18 ms 4188 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 4748 KB Correct.
2 Correct 17 ms 4660 KB Correct.
3 Correct 34 ms 11856 KB Correct.
4 Correct 14 ms 5404 KB Correct.
5 Correct 20 ms 4444 KB Correct.
6 Correct 18 ms 4696 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 4772 KB Correct.
2 Correct 7 ms 3932 KB Correct.
3 Correct 113 ms 14760 KB Correct.
4 Correct 95 ms 7964 KB Correct.
5 Correct 152 ms 13652 KB Correct.
6 Correct 69 ms 11736 KB Correct.
7 Correct 90 ms 8040 KB Correct.
8 Correct 82 ms 5972 KB Correct.
9 Correct 39 ms 4692 KB Correct.
10 Correct 39 ms 4944 KB Correct.
11 Correct 79 ms 5712 KB Correct.
12 Correct 40 ms 4808 KB Correct.
13 Correct 40 ms 4668 KB Correct.
14 Correct 85 ms 9972 KB Correct.
15 Correct 86 ms 6848 KB Correct.
16 Correct 38 ms 4824 KB Correct.
17 Correct 45 ms 4700 KB Correct.
18 Correct 40 ms 4688 KB Correct.
19 Correct 103 ms 5604 KB Correct.
20 Correct 3 ms 3416 KB Correct.
21 Correct 5 ms 3676 KB Correct.
22 Correct 6 ms 4236 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 4768 KB Correct.
2 Correct 13 ms 3932 KB Correct.
3 Correct 105 ms 20280 KB Correct.
4 Correct 95 ms 6484 KB Correct.
5 Correct 362 ms 13632 KB Correct.
6 Correct 148 ms 11736 KB Correct.
7 Correct 110 ms 10324 KB Correct.
8 Correct 91 ms 5712 KB Correct.
9 Correct 82 ms 4752 KB Correct.
10 Correct 62 ms 4700 KB Correct.
11 Correct 137 ms 4732 KB Correct.
12 Correct 76 ms 4700 KB Correct.
13 Correct 76 ms 4652 KB Correct.
14 Correct 178 ms 12424 KB Correct.
15 Correct 206 ms 10188 KB Correct.
16 Correct 131 ms 7760 KB Correct.
17 Correct 97 ms 5972 KB Correct.
18 Correct 69 ms 4768 KB Correct.
19 Correct 87 ms 4692 KB Correct.
20 Correct 76 ms 4768 KB Correct.
21 Correct 209 ms 5716 KB Correct.
22 Correct 5 ms 3416 KB Correct.
23 Correct 6 ms 3676 KB Correct.
24 Correct 12 ms 4252 KB Correct.