oj.uz

Submission #806734

# Submission time Handle Problem Language Result Execution time Memory
806734 2023-08-04T09:21:03 Z TheSahib Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 164676 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 = 90;

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, 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.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 2736 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3528 KB Correct.
2 Correct 23 ms 3460 KB Correct.
3 Correct 22 ms 3532 KB Correct.
4 Correct 23 ms 3412 KB Correct.
5 Correct 22 ms 3560 KB Correct.
6 Correct 23 ms 10452 KB Correct.
7 Correct 28 ms 10196 KB Correct.
8 Correct 17 ms 18044 KB Correct.
9 Correct 21 ms 2820 KB Correct.
10 Correct 20 ms 2816 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3412 KB Correct.
2 Correct 22 ms 3552 KB Correct.
3 Correct 26 ms 3580 KB Correct.
4 Correct 22 ms 2808 KB Correct.
5 Correct 22 ms 2808 KB Correct.
6 Correct 8 ms 9136 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 52508 KB Correct.
2 Correct 272 ms 3876 KB Correct.
3 Correct 234 ms 3916 KB Correct.
4 Correct 255 ms 3888 KB Correct.
5 Correct 209 ms 2892 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3540 KB Correct.
2 Correct 28 ms 3460 KB Correct.
3 Correct 21 ms 3472 KB Correct.
4 Correct 23 ms 10460 KB Correct.
5 Correct 19 ms 2800 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3584 KB Correct.
2 Correct 22 ms 3488 KB Correct.
3 Correct 50 ms 62036 KB Correct.
4 Correct 19 ms 8356 KB Correct.
5 Correct 20 ms 2772 KB Correct.
6 Correct 19 ms 3520 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 4460 KB Correct.
2 Correct 38 ms 5692 KB Correct.
3 Correct 574 ms 79572 KB Correct.
4 Correct 478 ms 20476 KB Correct.
5 Correct 1010 ms 66140 KB Correct.
6 Correct 463 ms 47044 KB Correct.
7 Correct 460 ms 22052 KB Correct.
8 Correct 479 ms 5816 KB Correct.
9 Correct 234 ms 4960 KB Correct.
10 Correct 238 ms 4536 KB Correct.
11 Correct 469 ms 3936 KB Correct.
12 Correct 251 ms 4544 KB Correct.
13 Correct 270 ms 4544 KB Correct.
14 Correct 391 ms 40456 KB Correct.
15 Correct 448 ms 13320 KB Correct.
16 Correct 238 ms 4496 KB Correct.
17 Correct 294 ms 4368 KB Correct.
18 Correct 295 ms 4476 KB Correct.
19 Correct 685 ms 4392 KB Correct.
20 Correct 20 ms 3132 KB Correct.
21 Correct 20 ms 3908 KB Correct.
22 Correct 32 ms 5896 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1241 ms 7548 KB Correct.
2 Correct 156 ms 11288 KB Correct.
3 Correct 768 ms 82592 KB Correct.
4 Correct 1161 ms 10696 KB Correct.
5 Execution timed out 3080 ms 164676 KB Time limit exceeded
6 Halted 0 ms 0 KB -