oj.uz

Submission #806727

# Submission time Handle Problem Language Result Execution time Memory
806727 2023-08-04T09:15:06 Z TheSahib Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 170064 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 = 160;
 
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 2788 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4056 KB Correct.
2 Correct 26 ms 3960 KB Correct.
3 Correct 24 ms 4040 KB Correct.
4 Correct 26 ms 4056 KB Correct.
5 Correct 25 ms 4024 KB Correct.
6 Correct 27 ms 15700 KB Correct.
7 Correct 33 ms 15500 KB Correct.
8 Correct 24 ms 28880 KB Correct.
9 Correct 23 ms 2848 KB Correct.
10 Correct 24 ms 2856 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4064 KB Correct.
2 Correct 26 ms 4088 KB Correct.
3 Correct 25 ms 4096 KB Correct.
4 Correct 24 ms 2872 KB Correct.
5 Correct 24 ms 2856 KB Correct.
6 Correct 10 ms 13604 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 84812 KB Correct.
2 Correct 299 ms 4336 KB Correct.
3 Correct 250 ms 4320 KB Correct.
4 Correct 277 ms 4260 KB Correct.
5 Correct 229 ms 2856 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4052 KB Correct.
2 Correct 23 ms 4124 KB Correct.
3 Correct 22 ms 4084 KB Correct.
4 Correct 27 ms 15784 KB Correct.
5 Correct 20 ms 2836 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4020 KB Correct.
2 Correct 20 ms 4052 KB Correct.
3 Correct 65 ms 103384 KB Correct.
4 Correct 19 ms 12116 KB Correct.
5 Correct 21 ms 2852 KB Correct.
6 Correct 26 ms 4112 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 4536 KB Correct.
2 Correct 47 ms 5716 KB Correct.
3 Correct 1016 ms 134308 KB Correct.
4 Correct 772 ms 32640 KB Correct.
5 Correct 1866 ms 84692 KB Correct.
6 Correct 798 ms 34380 KB Correct.
7 Correct 715 ms 35376 KB Correct.
8 Correct 695 ms 7608 KB Correct.
9 Correct 278 ms 4516 KB Correct.
10 Correct 268 ms 4468 KB Correct.
11 Correct 648 ms 4592 KB Correct.
12 Correct 283 ms 4532 KB Correct.
13 Correct 332 ms 4528 KB Correct.
14 Correct 657 ms 66424 KB Correct.
15 Correct 651 ms 19900 KB Correct.
16 Correct 276 ms 4520 KB Correct.
17 Correct 329 ms 4540 KB Correct.
18 Correct 330 ms 4544 KB Correct.
19 Correct 805 ms 4504 KB Correct.
20 Correct 23 ms 2852 KB Correct.
21 Correct 23 ms 4276 KB Correct.
22 Correct 52 ms 5596 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2393 ms 6392 KB Correct.
2 Correct 320 ms 8844 KB Correct.
3 Correct 1110 ms 137352 KB Correct.
4 Correct 2798 ms 13996 KB Correct.
5 Execution timed out 3025 ms 170064 KB Time limit exceeded
6 Halted 0 ms 0 KB -