oj.uz

Submission #806724

# Submission time Handle Problem Language Result Execution time Memory
806724 2023-08-04T09:12:57 Z TheSahib Cyberland (APIO23_cyberland) C++17
97 / 100
 2003 ms 60068 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
 
#define ll long long
using namespace std;
 
const ll oo = 1e18;
const int MAX = 1e5 + 5;
const int MAXK = 60;
 
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][MAXK + 1];
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 = min(MAXK, 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 2772 KB Correct.
2 Correct 20 ms 2800 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3308 KB Correct.
2 Correct 26 ms 3284 KB Correct.
3 Correct 32 ms 3296 KB Correct.
4 Correct 25 ms 3276 KB Correct.
5 Correct 25 ms 3260 KB Correct.
6 Correct 30 ms 8172 KB Correct.
7 Correct 35 ms 7968 KB Correct.
8 Correct 17 ms 13468 KB Correct.
9 Correct 23 ms 2764 KB Correct.
10 Correct 22 ms 2756 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3276 KB Correct.
2 Correct 26 ms 3228 KB Correct.
3 Correct 26 ms 3324 KB Correct.
4 Correct 24 ms 2772 KB Correct.
5 Correct 24 ms 2772 KB Correct.
6 Correct 8 ms 7380 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 39168 KB Correct.
2 Correct 296 ms 3548 KB Correct.
3 Correct 255 ms 3484 KB Correct.
4 Correct 273 ms 3428 KB Correct.
5 Correct 242 ms 2780 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3284 KB Correct.
2 Correct 32 ms 3332 KB Correct.
3 Correct 23 ms 3304 KB Correct.
4 Correct 25 ms 8200 KB Correct.
5 Correct 20 ms 2772 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3284 KB Correct.
2 Correct 20 ms 3312 KB Correct.
3 Correct 50 ms 44260 KB Correct.
4 Correct 16 ms 6856 KB Correct.
5 Correct 23 ms 2780 KB Correct.
6 Correct 22 ms 3364 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 3656 KB Correct.
2 Correct 46 ms 4396 KB Correct.
3 Correct 1016 ms 60068 KB Correct.
4 Correct 771 ms 15796 KB Correct.
5 Correct 2003 ms 56876 KB Correct.
6 Correct 805 ms 26360 KB Correct.
7 Correct 705 ms 16788 KB Correct.
8 Correct 675 ms 4876 KB Correct.
9 Correct 279 ms 3736 KB Correct.
10 Correct 297 ms 3696 KB Correct.
11 Correct 651 ms 3680 KB Correct.
12 Correct 287 ms 3648 KB Correct.
13 Correct 319 ms 3792 KB Correct.
14 Correct 620 ms 30304 KB Correct.
15 Correct 664 ms 10180 KB Correct.
16 Correct 280 ms 3656 KB Correct.
17 Correct 347 ms 3776 KB Correct.
18 Correct 356 ms 3712 KB Correct.
19 Correct 804 ms 3724 KB Correct.
20 Correct 23 ms 2772 KB Correct.
21 Correct 22 ms 3448 KB Correct.
22 Correct 46 ms 4792 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 809 ms 4180 KB Correct.
2 Correct 110 ms 5120 KB Correct.
3 Incorrect 660 ms 59076 KB Wrong Answer.
4 Halted 0 ms 0 KB -