Submission #1030863

# Submission time Handle Problem Language Result Execution time Memory
1030863 2024-07-22T10:57:37 Z amine_aroua Cyberland (APIO23_cyberland) C++17
100 / 100
129 ms 74848 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;
}
# Verdict Execution time Memory Grader output
1 Correct 14 ms 856 KB Correct.
2 Correct 13 ms 752 KB Correct.
# Verdict Execution time Memory Grader output
1 Correct 15 ms 1624 KB Correct.
2 Correct 23 ms 1884 KB Correct.
3 Correct 17 ms 1628 KB Correct.
4 Correct 18 ms 1884 KB Correct.
5 Correct 18 ms 1884 KB Correct.
6 Correct 15 ms 4752 KB Correct.
7 Correct 20 ms 4700 KB Correct.
8 Correct 10 ms 7948 KB Correct.
9 Correct 18 ms 1372 KB Correct.
10 Correct 17 ms 1372 KB Correct.
# Verdict Execution time Memory Grader output
1 Correct 19 ms 1824 KB Correct.
2 Correct 18 ms 1804 KB Correct.
3 Correct 16 ms 1720 KB Correct.
4 Correct 17 ms 1372 KB Correct.
5 Correct 17 ms 1372 KB Correct.
6 Correct 4 ms 3420 KB Correct.
# Verdict Execution time Memory Grader output
1 Correct 25 ms 23388 KB Correct.
2 Correct 16 ms 1752 KB Correct.
3 Correct 17 ms 1660 KB Correct.
4 Correct 16 ms 1748 KB Correct.
5 Correct 18 ms 1372 KB Correct.
# Verdict Execution time Memory Grader output
1 Correct 17 ms 1672 KB Correct.
2 Correct 19 ms 1884 KB Correct.
3 Correct 19 ms 1808 KB Correct.
4 Correct 19 ms 4700 KB Correct.
5 Correct 17 ms 1372 KB Correct.
# Verdict Execution time Memory Grader output
1 Correct 21 ms 1724 KB Correct.
2 Correct 17 ms 1624 KB Correct.
3 Correct 37 ms 29876 KB Correct.
4 Correct 13 ms 3316 KB Correct.
5 Correct 18 ms 1372 KB Correct.
6 Correct 18 ms 1736 KB Correct.
# Verdict Execution time Memory Grader output
1 Correct 18 ms 1764 KB Correct.
2 Correct 3 ms 1116 KB Correct.
3 Correct 56 ms 28908 KB Correct.
4 Correct 36 ms 9156 KB Correct.
5 Correct 36 ms 18260 KB Correct.
6 Correct 21 ms 9308 KB Correct.
7 Correct 35 ms 7988 KB Correct.
8 Correct 37 ms 3076 KB Correct.
9 Correct 17 ms 1732 KB Correct.
10 Correct 18 ms 1652 KB Correct.
11 Correct 36 ms 2636 KB Correct.
12 Correct 18 ms 1720 KB Correct.
13 Correct 34 ms 1816 KB Correct.
14 Correct 36 ms 10412 KB Correct.
15 Correct 35 ms 4576 KB Correct.
16 Correct 17 ms 1828 KB Correct.
17 Correct 19 ms 1844 KB Correct.
18 Correct 20 ms 1856 KB Correct.
19 Correct 34 ms 2744 KB Correct.
20 Correct 2 ms 604 KB Correct.
21 Correct 2 ms 768 KB Correct.
22 Correct 2 ms 1116 KB Correct.
# Verdict Execution time Memory Grader output
1 Correct 21 ms 2028 KB Correct.
2 Correct 3 ms 1628 KB Correct.
3 Correct 87 ms 74848 KB Correct.
4 Correct 42 ms 4688 KB Correct.
5 Correct 36 ms 29520 KB Correct.
6 Correct 22 ms 12372 KB Correct.
7 Correct 38 ms 14592 KB Correct.
8 Correct 38 ms 3116 KB Correct.
9 Correct 20 ms 2092 KB Correct.
10 Correct 36 ms 2044 KB Correct.
11 Correct 129 ms 1596 KB Correct.
12 Correct 22 ms 2152 KB Correct.
13 Correct 20 ms 2144 KB Correct.
14 Correct 69 ms 29780 KB Correct.
15 Correct 49 ms 35908 KB Correct.
16 Correct 42 ms 13300 KB Correct.
17 Correct 36 ms 4416 KB Correct.
18 Correct 19 ms 2108 KB Correct.
19 Correct 21 ms 2260 KB Correct.
20 Correct 22 ms 2080 KB Correct.
21 Correct 37 ms 2920 KB Correct.
22 Correct 2 ms 604 KB Correct.
23 Correct 2 ms 968 KB Correct.
24 Correct 3 ms 1372 KB Correct.