oj.uz

Submission #806725

# Submission time Handle Problem Language Result Execution time Memory
806725 2023-08-04T09:14:16 Z TheSahib Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 168664 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 = 200;
 
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 23 ms 2772 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4308 KB Correct.
2 Correct 26 ms 4340 KB Correct.
3 Correct 30 ms 4308 KB Correct.
4 Correct 34 ms 4380 KB Correct.
5 Correct 33 ms 4376 KB Correct.
6 Correct 28 ms 18884 KB Correct.
7 Correct 35 ms 18488 KB Correct.
8 Correct 27 ms 34964 KB Correct.
9 Correct 23 ms 2772 KB Correct.
10 Correct 22 ms 2900 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 4356 KB Correct.
2 Correct 38 ms 4392 KB Correct.
3 Correct 25 ms 4416 KB Correct.
4 Correct 24 ms 2772 KB Correct.
5 Correct 28 ms 2772 KB Correct.
6 Correct 13 ms 16080 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 103048 KB Correct.
2 Correct 294 ms 4648 KB Correct.
3 Correct 252 ms 4628 KB Correct.
4 Correct 272 ms 4608 KB Correct.
5 Correct 253 ms 2884 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4376 KB Correct.
2 Correct 23 ms 4408 KB Correct.
3 Correct 24 ms 4364 KB Correct.
4 Correct 28 ms 18772 KB Correct.
5 Correct 19 ms 2772 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4452 KB Correct.
2 Correct 20 ms 4424 KB Correct.
3 Correct 67 ms 127064 KB Correct.
4 Correct 19 ms 14316 KB Correct.
5 Correct 21 ms 2884 KB Correct.
6 Correct 22 ms 4436 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 4844 KB Correct.
2 Correct 48 ms 6212 KB Correct.
3 Correct 1120 ms 164024 KB Correct.
4 Correct 752 ms 39320 KB Correct.
5 Correct 1924 ms 95704 KB Correct.
6 Correct 773 ms 37608 KB Correct.
7 Correct 723 ms 42828 KB Correct.
8 Correct 689 ms 8648 KB Correct.
9 Correct 304 ms 4832 KB Correct.
10 Correct 281 ms 4708 KB Correct.
11 Correct 674 ms 5008 KB Correct.
12 Correct 291 ms 4840 KB Correct.
13 Correct 312 ms 4972 KB Correct.
14 Correct 649 ms 80888 KB Correct.
15 Correct 709 ms 23808 KB Correct.
16 Correct 278 ms 4952 KB Correct.
17 Correct 343 ms 4764 KB Correct.
18 Correct 327 ms 4816 KB Correct.
19 Correct 784 ms 4816 KB Correct.
20 Correct 25 ms 2876 KB Correct.
21 Correct 23 ms 4568 KB Correct.
22 Correct 48 ms 5776 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2929 ms 7164 KB Correct.
2 Correct 401 ms 10376 KB Correct.
3 Correct 1160 ms 168664 KB Correct.
4 Execution timed out 3032 ms 16396 KB Time limit exceeded
5 Halted 0 ms 0 KB -