oj.uz

Submission #806728

# Submission time Handle Problem Language Result Execution time Memory
806728 2023-08-04T09:15:59 Z TheSahib Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 143340 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 = 120;
 
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 22 ms 2828 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3784 KB Correct.
2 Correct 26 ms 3716 KB Correct.
3 Correct 25 ms 3728 KB Correct.
4 Correct 31 ms 3816 KB Correct.
5 Correct 25 ms 3740 KB Correct.
6 Correct 26 ms 12756 KB Correct.
7 Correct 34 ms 12572 KB Correct.
8 Correct 21 ms 22740 KB Correct.
9 Correct 23 ms 2796 KB Correct.
10 Correct 22 ms 2772 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3744 KB Correct.
2 Correct 26 ms 3668 KB Correct.
3 Correct 24 ms 3788 KB Correct.
4 Correct 24 ms 2816 KB Correct.
5 Correct 24 ms 2772 KB Correct.
6 Correct 9 ms 11092 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 66572 KB Correct.
2 Correct 302 ms 4076 KB Correct.
3 Correct 290 ms 3996 KB Correct.
4 Correct 273 ms 3988 KB Correct.
5 Correct 249 ms 2840 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3744 KB Correct.
2 Correct 27 ms 3696 KB Correct.
3 Correct 29 ms 3764 KB Correct.
4 Correct 26 ms 12708 KB Correct.
5 Correct 19 ms 2772 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3720 KB Correct.
2 Correct 20 ms 3796 KB Correct.
3 Correct 55 ms 79736 KB Correct.
4 Correct 17 ms 10084 KB Correct.
5 Correct 21 ms 2820 KB Correct.
6 Correct 21 ms 3796 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 4184 KB Correct.
2 Correct 49 ms 5128 KB Correct.
3 Correct 1192 ms 104584 KB Correct.
4 Correct 773 ms 25936 KB Correct.
5 Correct 1859 ms 73648 KB Correct.
6 Correct 765 ms 31092 KB Correct.
7 Correct 704 ms 27984 KB Correct.
8 Correct 682 ms 6736 KB Correct.
9 Correct 277 ms 4212 KB Correct.
10 Correct 272 ms 4092 KB Correct.
11 Correct 686 ms 4168 KB Correct.
12 Correct 340 ms 4224 KB Correct.
13 Correct 341 ms 4264 KB Correct.
14 Correct 636 ms 51944 KB Correct.
15 Correct 695 ms 16008 KB Correct.
16 Correct 286 ms 4172 KB Correct.
17 Correct 387 ms 4192 KB Correct.
18 Correct 348 ms 4176 KB Correct.
19 Correct 866 ms 4156 KB Correct.
20 Correct 23 ms 2852 KB Correct.
21 Correct 27 ms 4012 KB Correct.
22 Correct 49 ms 5152 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1943 ms 5440 KB Correct.
2 Correct 242 ms 7360 KB Correct.
3 Correct 1184 ms 106048 KB Correct.
4 Correct 2362 ms 11436 KB Correct.
5 Execution timed out 3065 ms 143340 KB Time limit exceeded
6 Halted 0 ms 0 KB -