oj.uz

Submission #985445

# Submission time Handle Problem Language Result Execution time Memory
985445 2024-05-17T20:45:06 Z oviyan_gandhi Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 30800 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long

#define MX 100000
int32_t powers[MX];
vector<pair<int,long double>> adj[MX];
priority_queue<pair<int,pair<long double,int>>,vector<pair<int,pair<long double,int>>>,greater<>> q;
bool visited[MX];

void dfs(int x){
    if(visited[x])return;
    visited[x]=true;
    if(powers[x]==0)q.emplace(0, make_pair(0,x));
    for(auto[dest,c]:adj[x])dfs(dest);
}

double solve(int32_t N, int32_t M, int32_t K, int32_t H, vector<int32_t> x, vector<int32_t> y, vector<int32_t> c, vector<int32_t> arr) {
    K = min(K, 67);
    for (int i = 0; i < N; i++){
        powers[i] = arr[i];
        adj[i].clear();
    }
    while(!q.empty())q.pop();
    fill(visited, visited+N, false);
    powers[0] = 0;
    visited[H]=true;
    for(int i=0;i<M;i++){
        adj[x[i]].emplace_back(y[i],c[i]);
        adj[y[i]].emplace_back(x[i],c[i]);
    }
    long double ans = 4e15;
    dfs(0);
    vector<vector<bool>> vis(N,vector<bool>(K+1));
    while(!q.empty()){
        auto [uses,curr] = q.top();q.pop();
        auto [tim,idx] = curr;
        if(idx==H){
            ans = min(ans,tim);
            continue;
        }
        if(vis[idx][uses])continue;
        vis[idx][uses]=true;
        for(auto[dest,cost]:adj[idx]){
            if(!vis[dest][uses])q.emplace(uses,make_pair(tim+cost,dest));
            if(powers[dest]==2 and uses<K and !vis[dest][uses+1])q.emplace(uses+1,make_pair((tim+cost)/(long double)(2),dest));
        }
    }
    return ans>=4e15 ? -1 : ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2904 KB Correct.
2 Correct 17 ms 2908 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2904 KB Correct.
2 Correct 26 ms 2908 KB Correct.
3 Correct 25 ms 2908 KB Correct.
4 Correct 26 ms 3160 KB Correct.
5 Correct 27 ms 2904 KB Correct.
6 Correct 24 ms 4896 KB Correct.
7 Correct 35 ms 4944 KB Correct.
8 Correct 19 ms 6748 KB Correct.
9 Correct 24 ms 2856 KB Correct.
10 Correct 28 ms 2872 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3124 KB Correct.
2 Correct 37 ms 3120 KB Correct.
3 Correct 28 ms 3112 KB Correct.
4 Correct 28 ms 2652 KB Correct.
5 Correct 34 ms 2904 KB Correct.
6 Correct 8 ms 4640 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 15532 KB Correct.
2 Correct 239 ms 3168 KB Correct.
3 Correct 208 ms 3148 KB Correct.
4 Correct 231 ms 3056 KB Correct.
5 Correct 138 ms 2648 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3160 KB Correct.
2 Correct 26 ms 3164 KB Correct.
3 Correct 26 ms 3164 KB Correct.
4 Correct 31 ms 5652 KB Correct.
5 Correct 22 ms 2908 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3160 KB Correct.
2 Correct 24 ms 3160 KB Correct.
3 Correct 42 ms 17756 KB Correct.
4 Correct 20 ms 5200 KB Correct.
5 Correct 28 ms 2908 KB Correct.
6 Correct 26 ms 3164 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 3412 KB Correct.
2 Correct 70 ms 3428 KB Correct.
3 Correct 869 ms 22672 KB Correct.
4 Correct 355 ms 7728 KB Correct.
5 Correct 1523 ms 24004 KB Correct.
6 Correct 1242 ms 26296 KB Correct.
7 Correct 357 ms 7860 KB Correct.
8 Correct 308 ms 3912 KB Correct.
9 Correct 321 ms 3292 KB Correct.
10 Correct 307 ms 3280 KB Correct.
11 Correct 290 ms 3336 KB Correct.
12 Correct 322 ms 3280 KB Correct.
13 Correct 348 ms 3660 KB Correct.
14 Correct 353 ms 13204 KB Correct.
15 Correct 344 ms 5572 KB Correct.
16 Correct 338 ms 3420 KB Correct.
17 Correct 374 ms 3412 KB Correct.
18 Correct 369 ms 3444 KB Correct.
19 Correct 796 ms 3408 KB Correct.
20 Correct 22 ms 2648 KB Correct.
21 Correct 23 ms 2904 KB Correct.
22 Correct 100 ms 5632 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 824 ms 3380 KB Correct.
2 Correct 130 ms 3420 KB Correct.
3 Correct 348 ms 30800 KB Correct.
4 Correct 410 ms 4544 KB Correct.
5 Execution timed out 3056 ms 23184 KB Time limit exceeded
6 Halted 0 ms 0 KB -