oj.uz

Submission #806679

# Submission time Handle Problem Language Result Execution time Memory
806679 2023-08-04T08:47:46 Z TheSahib Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 49796 KB 
#include "cyberland.h"
#include <bits/stdc++.h>

#define ll long long
using namespace std;

const ll oo = 1e18;
const int MAX = 1e5 + 5;

struct edge{
    int u, c;
};

int n, k, f;
int A[MAX];
vector<edge> g[MAX];
bool visited[MAX];

vector<int> starts;
void dfs(int node){
    visited[node] = 1;
    for(auto& e:g[node]){
        if(visited[e.u]) continue;
        dfs(e.u);
    }
}

double dist[MAX][32];
void dijkstra(){
    set<pair<double, pair<int, int>>> st;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= k; j++)
        {
            dist[i][j] = oo;
        }
    }
    
    for(int a:starts){
        dist[a][k] = 0;
        st.insert({0, {a, k}});
    }
    while(!st.empty()){
        double d = st.begin()->first;
        int node = st.begin()->second.first;
        int l = st.begin()->second.second;
        st.erase(st.begin());

        for(auto& e:g[node]){
            double b = d + e.c;
            
            if(b < dist[e.u][l]){
                st.erase({dist[e.u][l], {e.u, l}});
                dist[e.u][l] = b;
                st.insert({dist[e.u][l], {e.u, l}});
            }
            if(l == 0 || A[e.u] != 2) continue;
            if(b / 2 < dist[e.u][l - 1]){
                st.erase({dist[e.u][l - 1], {e.u, l - 1}});
                dist[e.u][l - 1] = b / 2;
                st.insert({dist[e.u][l - 1], {e.u, l - 1}});
            }
        }
    }
}


double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    n = N;
    k = K;
    f = H;
    starts.clear();
    for (int i = 0; i < n; i++)
    {
        A[i] = arr[i];
        g[i].clear();
        visited[i] = 0;
    }
    
    for (int i = 0; i < M; i++)
    {
        g[x[i]].push_back({y[i], c[i]});
        g[y[i]].push_back({x[i], c[i]});
    }
    g[f].clear();
    dfs(0);
    starts.push_back(0);
    for (int i = 0; i < n; i++)
    {
        if(visited[i] && A[i] == 0){
            starts.push_back(i);
        }
    }
    dijkstra();
    double ans = oo;
    for(int i = 0; i <= k; ++i){
        ans = min(ans, dist[f][i]);
    }
    if(ans == oo){
        return -1;
    }
    else{
        return ans;
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2828 KB Correct.
2 Correct 20 ms 3064 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3012 KB Correct.
2 Correct 26 ms 3076 KB Correct.
3 Correct 26 ms 2968 KB Correct.
4 Correct 29 ms 3028 KB Correct.
5 Correct 27 ms 3032 KB Correct.
6 Correct 23 ms 5844 KB Correct.
7 Correct 36 ms 5816 KB Correct.
8 Correct 15 ms 9120 KB Correct.
9 Correct 33 ms 2744 KB Correct.
10 Correct 24 ms 2688 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3064 KB Correct.
2 Correct 27 ms 3968 KB Correct.
3 Correct 26 ms 3976 KB Correct.
4 Correct 25 ms 3628 KB Correct.
5 Correct 26 ms 3648 KB Correct.
6 Correct 9 ms 5716 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 26008 KB Correct.
2 Correct 333 ms 4300 KB Correct.
3 Correct 264 ms 4268 KB Correct.
4 Correct 279 ms 4256 KB Correct.
5 Correct 233 ms 3692 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3036 KB Correct.
2 Correct 24 ms 3116 KB Correct.
3 Correct 27 ms 3196 KB Correct.
4 Correct 28 ms 6004 KB Correct.
5 Correct 21 ms 2644 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3028 KB Correct.
2 Correct 21 ms 4012 KB Correct.
3 Correct 46 ms 28112 KB Correct.
4 Correct 19 ms 5856 KB Correct.
5 Correct 22 ms 3620 KB Correct.
6 Correct 25 ms 4004 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 3524 KB Correct.
2 Correct 45 ms 4100 KB Correct.
3 Correct 989 ms 39464 KB Correct.
4 Correct 731 ms 11944 KB Correct.
5 Correct 1930 ms 49796 KB Correct.
6 Correct 720 ms 25060 KB Correct.
7 Correct 722 ms 12264 KB Correct.
8 Correct 659 ms 5172 KB Correct.
9 Correct 276 ms 4460 KB Correct.
10 Correct 262 ms 4448 KB Correct.
11 Correct 628 ms 4320 KB Correct.
12 Correct 310 ms 4468 KB Correct.
13 Correct 303 ms 4568 KB Correct.
14 Correct 625 ms 20824 KB Correct.
15 Correct 650 ms 8460 KB Correct.
16 Correct 272 ms 4468 KB Correct.
17 Correct 326 ms 4480 KB Correct.
18 Correct 319 ms 4556 KB Correct.
19 Correct 773 ms 4512 KB Correct.
20 Correct 23 ms 2816 KB Correct.
21 Correct 23 ms 3332 KB Correct.
22 Correct 49 ms 4820 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3076 ms 11852 KB Time limit exceeded
2 Halted 0 ms 0 KB -