oj.uz

Submission #806739

# Submission time Handle Problem Language Result Execution time Memory
806739 2023-08-04T09:23:41 Z TheSahib Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 159648 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
 
#define ll long long
#define pii pair<int, int>
using namespace std;
 
const ll oo = 1e18;
const int MAX = 1e5 + 5;
const int MAXK = 70;

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(){
    priority_queue<pair<double, pii>> 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.push({0, {a, k}});
    }
    while(!st.empty()){
        double d = -st.top().first;
        int node = st.top().second.first;
        int l = st.top().second.second;
        st.pop();
        if(dist[node][l] < d) continue;
 
        for(auto& e:g[node]){
            double b = d + e.c;
            
            if(b < dist[e.u][l]){
                dist[e.u][l] = b;
                st.push({-dist[e.u][l], {e.u, l}});
            }
            if(l == 0 || A[e.u] != 2) continue;
            if(b / 2 < dist[e.u][l - 1]){
                dist[e.u][l - 1] = b / 2;
                st.push({-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 18 ms 3028 KB Correct.
2 Correct 19 ms 3064 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3528 KB Correct.
2 Correct 24 ms 3740 KB Correct.
3 Correct 23 ms 3688 KB Correct.
4 Correct 26 ms 3708 KB Correct.
5 Correct 24 ms 3716 KB Correct.
6 Correct 23 ms 9044 KB Correct.
7 Correct 29 ms 9272 KB Correct.
8 Correct 17 ms 15272 KB Correct.
9 Correct 22 ms 3020 KB Correct.
10 Correct 24 ms 3028 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3660 KB Correct.
2 Correct 30 ms 3628 KB Correct.
3 Correct 23 ms 3604 KB Correct.
4 Correct 23 ms 2972 KB Correct.
5 Correct 24 ms 3040 KB Correct.
6 Correct 8 ms 7964 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 44008 KB Correct.
2 Correct 267 ms 4000 KB Correct.
3 Correct 234 ms 3956 KB Correct.
4 Correct 260 ms 3972 KB Correct.
5 Correct 227 ms 3056 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3656 KB Correct.
2 Correct 23 ms 3812 KB Correct.
3 Correct 23 ms 3680 KB Correct.
4 Correct 25 ms 9268 KB Correct.
5 Correct 20 ms 2944 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3876 KB Correct.
2 Correct 20 ms 3580 KB Correct.
3 Correct 52 ms 50728 KB Correct.
4 Correct 17 ms 7628 KB Correct.
5 Correct 23 ms 3076 KB Correct.
6 Correct 25 ms 3688 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 4584 KB Correct.
2 Correct 39 ms 5572 KB Correct.
3 Correct 639 ms 65204 KB Correct.
4 Correct 481 ms 17624 KB Correct.
5 Correct 1024 ms 61168 KB Correct.
6 Correct 482 ms 45904 KB Correct.
7 Correct 473 ms 18552 KB Correct.
8 Correct 472 ms 5660 KB Correct.
9 Correct 248 ms 4900 KB Correct.
10 Correct 239 ms 4564 KB Correct.
11 Correct 480 ms 4260 KB Correct.
12 Correct 260 ms 4640 KB Correct.
13 Correct 265 ms 4580 KB Correct.
14 Correct 394 ms 33784 KB Correct.
15 Correct 450 ms 11808 KB Correct.
16 Correct 255 ms 4492 KB Correct.
17 Correct 296 ms 4520 KB Correct.
18 Correct 287 ms 4580 KB Correct.
19 Correct 686 ms 4700 KB Correct.
20 Correct 21 ms 3156 KB Correct.
21 Correct 20 ms 3852 KB Correct.
22 Correct 33 ms 5960 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 941 ms 7512 KB Correct.
2 Correct 128 ms 10068 KB Correct.
3 Correct 591 ms 67440 KB Correct.
4 Correct 1000 ms 8908 KB Correct.
5 Execution timed out 3025 ms 159648 KB Time limit exceeded
6 Halted 0 ms 0 KB -