oj.uz

Submission #806806

# Submission time Handle Problem Language Result Execution time Memory
806806 2023-08-04T10:01:29 Z TheSahib Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 160964 KB 
#pragma optimize("Ofast")

#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;
const int MAXK = 70;

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];

priority_queue<pair<double, pii>> st;
void dijkstra(){
    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;
    }
}

Compilation message

cyberland.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Ofast")
      |

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3028 KB Correct.
2 Correct 18 ms 3036 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 4252 KB Correct.
2 Correct 24 ms 4360 KB Correct.
3 Correct 22 ms 4344 KB Correct.
4 Correct 23 ms 4364 KB Correct.
5 Correct 24 ms 4392 KB Correct.
6 Correct 22 ms 9684 KB Correct.
7 Correct 29 ms 9812 KB Correct.
8 Correct 16 ms 15508 KB Correct.
9 Correct 22 ms 3668 KB Correct.
10 Correct 21 ms 3660 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 4300 KB Correct.
2 Correct 27 ms 4308 KB Correct.
3 Correct 23 ms 4312 KB Correct.
4 Correct 23 ms 3668 KB Correct.
5 Correct 23 ms 3664 KB Correct.
6 Correct 8 ms 8020 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 44864 KB Correct.
2 Correct 274 ms 4552 KB Correct.
3 Correct 241 ms 4416 KB Correct.
4 Correct 259 ms 4428 KB Correct.
5 Correct 217 ms 3692 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 4308 KB Correct.
2 Correct 29 ms 4400 KB Correct.
3 Correct 30 ms 4300 KB Correct.
4 Correct 24 ms 9940 KB Correct.
5 Correct 19 ms 3532 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4368 KB Correct.
2 Correct 21 ms 4308 KB Correct.
3 Correct 52 ms 52004 KB Correct.
4 Correct 16 ms 8000 KB Correct.
5 Correct 20 ms 3628 KB Correct.
6 Correct 24 ms 4384 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 4728 KB Correct.
2 Correct 40 ms 4964 KB Correct.
3 Correct 640 ms 66860 KB Correct.
4 Correct 495 ms 19048 KB Correct.
5 Correct 1016 ms 62420 KB Correct.
6 Correct 471 ms 46944 KB Correct.
7 Correct 452 ms 20104 KB Correct.
8 Correct 471 ms 6992 KB Correct.
9 Correct 228 ms 4916 KB Correct.
10 Correct 229 ms 4768 KB Correct.
11 Correct 462 ms 5628 KB Correct.
12 Correct 244 ms 4804 KB Correct.
13 Correct 260 ms 4780 KB Correct.
14 Correct 378 ms 35172 KB Correct.
15 Correct 461 ms 12796 KB Correct.
16 Correct 240 ms 4784 KB Correct.
17 Correct 283 ms 4852 KB Correct.
18 Correct 278 ms 4800 KB Correct.
19 Correct 686 ms 5728 KB Correct.
20 Correct 20 ms 3152 KB Correct.
21 Correct 20 ms 3600 KB Correct.
22 Correct 36 ms 5916 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 913 ms 6032 KB Correct.
2 Correct 123 ms 8096 KB Correct.
3 Correct 637 ms 69232 KB Correct.
4 Correct 1040 ms 9740 KB Correct.
5 Execution timed out 3061 ms 160964 KB Time limit exceeded
6 Halted 0 ms 0 KB -