oj.uz

Submission #1037388

# Submission time Handle Problem Language Result Execution time Memory
1037388 2024-07-28T18:34:07 Z aaaaaarroz Cyberland (APIO23_cyberland) C++17
100 / 100
 118 ms 74836 KB 
    #include "cyberland.h"
    #include <bits/stdc++.h>
    using namespace std;
    void dfs(int x , vector<bool>&reach , vector<vector<pair<int ,int>>> &adj , int H){
        if(x == H || reach[x]){
            return;
        }
        reach[x] = 1;
        for(auto [u , cost] : adj[x]){
            dfs(u , reach , adj , H);
        }    
    }
    using Node = tuple<double , int , int>;
    priority_queue<Node , vector<Node> , greater<Node>> pq;
    void upd(int x , int k , double d , vector<vector<double>> &dist){
        if(dist[x][k] > d){
            dist[x][k] = d;
            pq.push({d , x , k});
        }
    }
    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){
        pq = priority_queue<Node , vector<Node> , greater<Node>> ();
        K = min(K , 70);
        vector<vector<pair<int , int>>> adj(N);
        vector<bool> reach(N);
        vector<double> pwr(K + 1);
        pwr[0] = 1;
        for(int i = 1 ; i <= K ; i++){
            pwr[i] = pwr[i - 1]/2.0;
        } 
        for(int i = 0 ; i < M ; i++){
            adj[x[i]].push_back({y[i] , c[i]});
            adj[y[i]].push_back({x[i] , c[i]});
        }
        vector<vector<double>> dist(N , vector<double>(K + 1 , 1e18));
        arr[0] = 0;
        upd(H , 0 , 0 , dist);
        dfs(0 , reach ,adj ,H);
        while(!pq.empty()){
            auto [d , x , k] = pq.top();
            pq.pop();
            if(arr[x] == 0){
                return d;
            }
            for(auto [u , cost] : adj[x]){
                if(!reach[u])
                    continue;
                upd(u , k , cost*pwr[k] + d , dist);
                if(arr[x] == 2 && k < K){
                    int p = k + 1;
                    upd(u , p , cost*pwr[p] + d , dist);
                }
            }
        }
        return -1;
    }

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 856 KB Correct.
2 Correct 13 ms 856 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1624 KB Correct.
2 Correct 17 ms 1884 KB Correct.
3 Correct 17 ms 1624 KB Correct.
4 Correct 17 ms 1884 KB Correct.
5 Correct 17 ms 1880 KB Correct.
6 Correct 16 ms 4768 KB Correct.
7 Correct 20 ms 4732 KB Correct.
8 Correct 10 ms 8024 KB Correct.
9 Correct 18 ms 1476 KB Correct.
10 Correct 17 ms 1424 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1624 KB Correct.
2 Correct 17 ms 1800 KB Correct.
3 Correct 16 ms 1740 KB Correct.
4 Correct 17 ms 1372 KB Correct.
5 Correct 18 ms 1372 KB Correct.
6 Correct 4 ms 3428 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23444 KB Correct.
2 Correct 16 ms 1872 KB Correct.
3 Correct 15 ms 1808 KB Correct.
4 Correct 16 ms 1764 KB Correct.
5 Correct 18 ms 1372 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1928 KB Correct.
2 Correct 19 ms 1884 KB Correct.
3 Correct 19 ms 1848 KB Correct.
4 Correct 21 ms 4600 KB Correct.
5 Correct 17 ms 1372 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1724 KB Correct.
2 Correct 16 ms 1672 KB Correct.
3 Correct 38 ms 29940 KB Correct.
4 Correct 13 ms 3352 KB Correct.
5 Correct 20 ms 1304 KB Correct.
6 Correct 18 ms 1760 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1764 KB Correct.
2 Correct 3 ms 1116 KB Correct.
3 Correct 49 ms 29012 KB Correct.
4 Correct 35 ms 9088 KB Correct.
5 Correct 32 ms 18268 KB Correct.
6 Correct 21 ms 9308 KB Correct.
7 Correct 34 ms 7988 KB Correct.
8 Correct 35 ms 3092 KB Correct.
9 Correct 18 ms 1720 KB Correct.
10 Correct 18 ms 1660 KB Correct.
11 Correct 37 ms 2548 KB Correct.
12 Correct 18 ms 1720 KB Correct.
13 Correct 18 ms 1820 KB Correct.
14 Correct 38 ms 10532 KB Correct.
15 Correct 34 ms 4484 KB Correct.
16 Correct 18 ms 1828 KB Correct.
17 Correct 20 ms 1844 KB Correct.
18 Correct 18 ms 1800 KB Correct.
19 Correct 37 ms 2852 KB Correct.
20 Correct 2 ms 604 KB Correct.
21 Correct 2 ms 768 KB Correct.
22 Correct 3 ms 1116 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1996 KB Correct.
2 Correct 3 ms 1628 KB Correct.
3 Correct 79 ms 74836 KB Correct.
4 Correct 35 ms 4604 KB Correct.
5 Correct 34 ms 29332 KB Correct.
6 Correct 23 ms 12372 KB Correct.
7 Correct 41 ms 14700 KB Correct.
8 Correct 41 ms 2976 KB Correct.
9 Correct 21 ms 2044 KB Correct.
10 Correct 21 ms 1920 KB Correct.
11 Correct 118 ms 1788 KB Correct.
12 Correct 18 ms 2144 KB Correct.
13 Correct 20 ms 2144 KB Correct.
14 Correct 51 ms 29904 KB Correct.
15 Correct 49 ms 35800 KB Correct.
16 Correct 37 ms 13264 KB Correct.
17 Correct 40 ms 4540 KB Correct.
18 Correct 19 ms 2116 KB Correct.
19 Correct 21 ms 2356 KB Correct.
20 Correct 24 ms 2080 KB Correct.
21 Correct 39 ms 3044 KB Correct.
22 Correct 2 ms 600 KB Correct.
23 Correct 2 ms 1044 KB Correct.
24 Correct 2 ms 1412 KB Correct.