oj.uz

Submission #760469

# Submission time Handle Problem Language Result Execution time Memory
760469 2023-06-17T15:55:41 Z salmon Cyberland (APIO23_cyberland) C++17
100 / 100
 482 ms 134256 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;


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) {
    //10^5
    vector<pair<int,int>> adjlst[N];
    long double d[N][min(K + 10,70 + 10)];
    bool visited[N];
    queue<pair<long double,int>> pq;
    queue<int> q;
    vector<int> voots;
    vector<int> sootv;

    for(int i = 0; i < M; i++){
        adjlst[x[i]].push_back(make_pair(y[i],c[i]));
        adjlst[y[i]].push_back(make_pair(x[i],c[i]));
    }

    for(int i = 0; i < N; i++) visited[i] = false;

    for(int k = 0; k <= min(K,70); k++){
    for(int i = 0; i < N; i++) d[i][k] = -1;
    }

    visited[0] = true;

    q.push(0);

    while(!q.empty()){
        int i = q.front();
        q.pop();
        for(pair<int,int> ii : adjlst[i]){
            int j = ii.first;
            if(!visited[j]){
                visited[j] = true;
                if(arr[j] == 0) voots.push_back(j);
                if(arr[j] == 2) sootv.push_back(j);
                if(j != H) q.push(j);
            }
        }
    }

    voots.push_back(0);

    if(!visited[H]) return -1;

    for(int i : voots){
        d[i][0] = 0;
        pq.push(make_pair(0,i));
    }

    while(!pq.empty()){
        long double de = pq.front().first;
        int i = pq.front().second;
        pq.pop();

        if(d[i][0] == de && i != H){
            for(pair<int,int> j : adjlst[i]){
                if(d[j.first][0] == -1 || d[j.first][0] > de + j.second){
                    d[j.first][0] = de + j.second;
                    pq.push(make_pair(de + j.second, j.first));
                }
            }
        }
    }

    for(int k = 1; k <= min(K,70); k++){
        for(int i = 0; i < N; i++) d[i][k] = d[i][k - 1];

        for(int i : sootv){
            for(pair<int,int> j : adjlst[i]){
                if(d[j.first][k] == -1 || d[j.first][k] > d[i][k - 1]/2 + j.second){
                    d[j.first][k] = d[i][k - 1]/2 + j.second;
                    pq.push(make_pair(d[i][k - 1]/2 + j.second, j.first));
                }
            }
        }

        while(!pq.empty()){
            long double de = pq.front().first;
            int i = pq.front().second;
            pq.pop();

            if(d[i][k] == de && i != H){
                for(pair<int,int> j : adjlst[i]){
                    if(d[j.first][k] == -1 || d[j.first][k] > de + j.second){
                        d[j.first][k] = de + j.second;
                        pq.push(make_pair(de + j.second, j.first));
                    }
                }
            }
        }
    }

    return d[H][min(K,70)];
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 368 KB Correct.
2 Correct 18 ms 440 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1028 KB Correct.
2 Correct 29 ms 1012 KB Correct.
3 Correct 28 ms 1048 KB Correct.
4 Correct 29 ms 980 KB Correct.
5 Correct 29 ms 1036 KB Correct.
6 Correct 34 ms 7376 KB Correct.
7 Correct 43 ms 7176 KB Correct.
8 Correct 26 ms 14412 KB Correct.
9 Correct 26 ms 412 KB Correct.
10 Correct 26 ms 416 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1036 KB Correct.
2 Correct 29 ms 980 KB Correct.
3 Correct 27 ms 1072 KB Correct.
4 Correct 32 ms 420 KB Correct.
5 Correct 28 ms 428 KB Correct.
6 Correct 8 ms 6228 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 42060 KB Correct.
2 Correct 35 ms 1044 KB Correct.
3 Correct 32 ms 1116 KB Correct.
4 Correct 34 ms 1056 KB Correct.
5 Correct 34 ms 340 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1000 KB Correct.
2 Correct 26 ms 1060 KB Correct.
3 Correct 26 ms 1036 KB Correct.
4 Correct 37 ms 7252 KB Correct.
5 Correct 22 ms 400 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 980 KB Correct.
2 Correct 22 ms 1016 KB Correct.
3 Correct 67 ms 54552 KB Correct.
4 Correct 19 ms 5388 KB Correct.
5 Correct 24 ms 412 KB Correct.
6 Correct 24 ms 1052 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1008 KB Correct.
2 Correct 5 ms 1492 KB Correct.
3 Correct 194 ms 49404 KB Correct.
4 Correct 100 ms 12664 KB Correct.
5 Correct 130 ms 28876 KB Correct.
6 Correct 50 ms 11384 KB Correct.
7 Correct 111 ms 12876 KB Correct.
8 Correct 73 ms 2396 KB Correct.
9 Correct 30 ms 1072 KB Correct.
10 Correct 29 ms 1048 KB Correct.
11 Correct 73 ms 1176 KB Correct.
12 Correct 33 ms 1052 KB Correct.
13 Correct 38 ms 1184 KB Correct.
14 Correct 95 ms 16348 KB Correct.
15 Correct 80 ms 4644 KB Correct.
16 Correct 31 ms 1032 KB Correct.
17 Correct 35 ms 1084 KB Correct.
18 Correct 33 ms 1072 KB Correct.
19 Correct 71 ms 1036 KB Correct.
20 Correct 3 ms 340 KB Correct.
21 Correct 3 ms 980 KB Correct.
22 Correct 6 ms 1364 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 1620 KB Correct.
2 Correct 7 ms 2516 KB Correct.
3 Correct 482 ms 134256 KB Correct.
4 Correct 88 ms 5540 KB Correct.
5 Correct 213 ms 51252 KB Correct.
6 Correct 96 ms 17856 KB Correct.
7 Correct 137 ms 26128 KB Correct.
8 Correct 97 ms 2528 KB Correct.
9 Correct 43 ms 1672 KB Correct.
10 Correct 41 ms 1672 KB Correct.
11 Correct 144 ms 492 KB Correct.
12 Correct 47 ms 1652 KB Correct.
13 Correct 46 ms 1668 KB Correct.
14 Correct 269 ms 53192 KB Correct.
15 Correct 343 ms 66588 KB Correct.
16 Correct 159 ms 22564 KB Correct.
17 Correct 94 ms 5084 KB Correct.
18 Correct 45 ms 1600 KB Correct.
19 Correct 51 ms 1700 KB Correct.
20 Correct 53 ms 1800 KB Correct.
21 Correct 106 ms 1664 KB Correct.
22 Correct 4 ms 340 KB Correct.
23 Correct 4 ms 1492 KB Correct.
24 Correct 8 ms 1876 KB Correct.