oj.uz

Submission #806710

# Submission time Handle Problem Language Result Execution time Memory
806710 2023-08-04T09:07:35 Z TheSahib Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 91680 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;

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][32];
bool comp(pii a, pii b){
    return dist[a.first][a.second] <= dist[b.first][b.second];
}

void dijkstra(){
    set<pii, decltype(&comp)> st(&comp);
    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({a, k});
    }
    while(!st.empty()){
        
        int node = st.begin()->first;
        int l = st.begin()->second;
        double d = dist[node][l];
        st.erase(st.begin());


        for(auto& e:g[node]){
            double b = d + e.c;
            
            if(b < dist[e.u][l]){
                st.erase({e.u, l});
                dist[e.u][l] = b;
                st.insert({e.u, l});
            }
            if(l == 0 || A[e.u] != 2) continue;
            if(b / 2 < dist[e.u][l - 1]){
                st.erase({e.u, l - 1});
                dist[e.u][l - 1] = b / 2;
                st.insert({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 = 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 21 ms 2772 KB Correct.
2 Correct 20 ms 2764 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3096 KB Correct.
2 Correct 28 ms 3012 KB Correct.
3 Correct 26 ms 3040 KB Correct.
4 Correct 28 ms 3052 KB Correct.
5 Correct 31 ms 3028 KB Correct.
6 Correct 26 ms 5844 KB Correct.
7 Correct 33 ms 5844 KB Correct.
8 Correct 18 ms 8992 KB Correct.
9 Correct 28 ms 2752 KB Correct.
10 Correct 26 ms 2752 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3028 KB Correct.
2 Correct 29 ms 3072 KB Correct.
3 Correct 27 ms 3072 KB Correct.
4 Correct 26 ms 2752 KB Correct.
5 Correct 26 ms 2756 KB Correct.
6 Correct 8 ms 5460 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 477 ms 28688 KB Correct.
2 Correct 521 ms 3420 KB Correct.
3 Correct 457 ms 3460 KB Correct.
4 Correct 495 ms 3440 KB Correct.
5 Correct 377 ms 2856 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3028 KB Correct.
2 Correct 27 ms 3028 KB Correct.
3 Correct 30 ms 3080 KB Correct.
4 Correct 26 ms 6040 KB Correct.
5 Correct 22 ms 2760 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3092 KB Correct.
2 Correct 23 ms 3032 KB Correct.
3 Correct 45 ms 27048 KB Correct.
4 Correct 16 ms 5248 KB Correct.
5 Correct 22 ms 2732 KB Correct.
6 Correct 24 ms 3064 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 4248 KB Correct.
2 Correct 82 ms 5192 KB Correct.
3 Correct 1609 ms 37388 KB Correct.
4 Correct 1116 ms 10732 KB Correct.
5 Correct 2991 ms 91680 KB Correct.
6 Correct 1256 ms 59708 KB Correct.
7 Correct 1022 ms 11276 KB Correct.
8 Correct 952 ms 4128 KB Correct.
9 Correct 471 ms 4132 KB Correct.
10 Correct 493 ms 4252 KB Correct.
11 Correct 956 ms 3328 KB Correct.
12 Correct 512 ms 4304 KB Correct.
13 Correct 559 ms 4204 KB Correct.
14 Correct 1012 ms 19692 KB Correct.
15 Correct 997 ms 7404 KB Correct.
16 Correct 518 ms 4140 KB Correct.
17 Correct 611 ms 4076 KB Correct.
18 Correct 661 ms 4048 KB Correct.
19 Correct 1460 ms 4072 KB Correct.
20 Correct 34 ms 2772 KB Correct.
21 Correct 46 ms 3568 KB Correct.
22 Correct 93 ms 8468 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3077 ms 18324 KB Time limit exceeded
2 Halted 0 ms 0 KB -