oj.uz

Submission #806740

# Submission time Handle Problem Language Result Execution time Memory
806740 2023-08-04T09:24:25 Z TheSahib Cyberland (APIO23_cyberland) C++17
97 / 100
 1071 ms 59040 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 = 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(){
    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 2772 KB Correct.
2 Correct 18 ms 2772 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3276 KB Correct.
2 Correct 23 ms 3260 KB Correct.
3 Correct 22 ms 3240 KB Correct.
4 Correct 22 ms 3284 KB Correct.
5 Correct 22 ms 3280 KB Correct.
6 Correct 27 ms 8076 KB Correct.
7 Correct 32 ms 7928 KB Correct.
8 Correct 17 ms 13540 KB Correct.
9 Correct 20 ms 2716 KB Correct.
10 Correct 20 ms 2780 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3272 KB Correct.
2 Correct 22 ms 3312 KB Correct.
3 Correct 21 ms 3308 KB Correct.
4 Correct 22 ms 2772 KB Correct.
5 Correct 22 ms 2772 KB Correct.
6 Correct 7 ms 7124 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 38844 KB Correct.
2 Correct 269 ms 3652 KB Correct.
3 Correct 233 ms 3640 KB Correct.
4 Correct 252 ms 3676 KB Correct.
5 Correct 209 ms 2864 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3344 KB Correct.
2 Correct 24 ms 3284 KB Correct.
3 Correct 22 ms 3316 KB Correct.
4 Correct 23 ms 8152 KB Correct.
5 Correct 18 ms 2772 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3364 KB Correct.
2 Correct 18 ms 3284 KB Correct.
3 Correct 47 ms 44248 KB Correct.
4 Correct 16 ms 6828 KB Correct.
5 Correct 20 ms 2784 KB Correct.
6 Correct 25 ms 3300 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 4252 KB Correct.
2 Correct 38 ms 5308 KB Correct.
3 Correct 651 ms 57212 KB Correct.
4 Correct 485 ms 15368 KB Correct.
5 Correct 1071 ms 57816 KB Correct.
6 Correct 497 ms 44572 KB Correct.
7 Correct 456 ms 16500 KB Correct.
8 Correct 472 ms 4884 KB Correct.
9 Correct 233 ms 4808 KB Correct.
10 Correct 241 ms 4276 KB Correct.
11 Correct 466 ms 3684 KB Correct.
12 Correct 256 ms 4392 KB Correct.
13 Correct 269 ms 4224 KB Correct.
14 Correct 402 ms 29680 KB Correct.
15 Correct 469 ms 10224 KB Correct.
16 Correct 243 ms 4224 KB Correct.
17 Correct 292 ms 4132 KB Correct.
18 Correct 289 ms 4168 KB Correct.
19 Correct 702 ms 4084 KB Correct.
20 Correct 21 ms 3156 KB Correct.
21 Correct 20 ms 3612 KB Correct.
22 Correct 37 ms 5752 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 765 ms 6492 KB Correct.
2 Correct 106 ms 9924 KB Correct.
3 Incorrect 472 ms 59040 KB Wrong Answer.
4 Halted 0 ms 0 KB -