oj.uz

Submission #806723

# Submission time Handle Problem Language Result Execution time Memory
806723 2023-08-04T09:12:12 Z TheSahib Cyberland (APIO23_cyberland) C++17
97 / 100
 1985 ms 51268 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 = 40;
 
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 19 ms 2772 KB Correct.
2 Correct 19 ms 2748 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3112 KB Correct.
2 Correct 27 ms 3136 KB Correct.
3 Correct 25 ms 3156 KB Correct.
4 Correct 26 ms 3100 KB Correct.
5 Correct 26 ms 3096 KB Correct.
6 Correct 23 ms 6612 KB Correct.
7 Correct 34 ms 6484 KB Correct.
8 Correct 16 ms 10424 KB Correct.
9 Correct 24 ms 2760 KB Correct.
10 Correct 23 ms 2756 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 3076 KB Correct.
2 Correct 29 ms 3136 KB Correct.
3 Correct 25 ms 3192 KB Correct.
4 Correct 30 ms 2756 KB Correct.
5 Correct 25 ms 2772 KB Correct.
6 Correct 7 ms 6100 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 30076 KB Correct.
2 Correct 289 ms 3488 KB Correct.
3 Correct 246 ms 3336 KB Correct.
4 Correct 264 ms 3344 KB Correct.
5 Correct 224 ms 2772 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3156 KB Correct.
2 Correct 24 ms 3076 KB Correct.
3 Correct 24 ms 3164 KB Correct.
4 Correct 25 ms 6596 KB Correct.
5 Correct 22 ms 2752 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3172 KB Correct.
2 Correct 27 ms 3176 KB Correct.
3 Correct 44 ms 32424 KB Correct.
4 Correct 16 ms 5716 KB Correct.
5 Correct 23 ms 2744 KB Correct.
6 Correct 23 ms 3156 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 3596 KB Correct.
2 Correct 49 ms 4120 KB Correct.
3 Correct 994 ms 45120 KB Correct.
4 Correct 735 ms 12424 KB Correct.
5 Correct 1985 ms 51268 KB Correct.
6 Correct 818 ms 24760 KB Correct.
7 Correct 714 ms 13120 KB Correct.
8 Correct 676 ms 4428 KB Correct.
9 Correct 291 ms 3584 KB Correct.
10 Correct 264 ms 3548 KB Correct.
11 Correct 637 ms 3440 KB Correct.
12 Correct 301 ms 3532 KB Correct.
13 Correct 302 ms 3644 KB Correct.
14 Correct 631 ms 23100 KB Correct.
15 Correct 662 ms 8224 KB Correct.
16 Correct 273 ms 3540 KB Correct.
17 Correct 326 ms 3588 KB Correct.
18 Correct 321 ms 3536 KB Correct.
19 Correct 767 ms 3560 KB Correct.
20 Correct 23 ms 2784 KB Correct.
21 Correct 22 ms 3312 KB Correct.
22 Correct 52 ms 4812 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 4028 KB Correct.
2 Correct 63 ms 4436 KB Correct.
3 Incorrect 507 ms 44440 KB Wrong Answer.
4 Halted 0 ms 0 KB -