oj.uz

Submission #977894

# Submission time Handle Problem Language Result Execution time Memory
977894 2024-05-08T13:16:15 Z Unforgettablepl Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 64104 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

vector<int32_t> powers;
vector<vector<pair<int,long double>>> adj;
priority_queue<pair<int,pair<long double,int>>,vector<pair<int,pair<long double,int>>>,greater<>> q;
vector<bool> visited;

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) {
    swap(powers,arr);
    visited = vector<bool>(N);
    adj = vector<vector<pair<int,long double>>>(N);
    while(!q.empty())q.pop();
    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 19 ms 600 KB Correct.
2 Correct 26 ms 604 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 856 KB Correct.
2 Correct 31 ms 600 KB Correct.
3 Correct 29 ms 652 KB Correct.
4 Correct 30 ms 604 KB Correct.
5 Correct 29 ms 600 KB Correct.
6 Correct 29 ms 2452 KB Correct.
7 Correct 35 ms 2652 KB Correct.
8 Correct 23 ms 4704 KB Correct.
9 Correct 27 ms 348 KB Correct.
10 Correct 26 ms 536 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 744 KB Correct.
2 Correct 40 ms 748 KB Correct.
3 Correct 31 ms 600 KB Correct.
4 Correct 43 ms 504 KB Correct.
5 Correct 30 ms 520 KB Correct.
6 Correct 7 ms 2392 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 14684 KB Correct.
2 Correct 263 ms 816 KB Correct.
3 Correct 244 ms 1820 KB Correct.
4 Correct 247 ms 1800 KB Correct.
5 Correct 153 ms 1452 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 812 KB Correct.
2 Correct 30 ms 604 KB Correct.
3 Correct 38 ms 800 KB Correct.
4 Correct 40 ms 2968 KB Correct.
5 Correct 25 ms 348 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 776 KB Correct.
2 Correct 28 ms 604 KB Correct.
3 Correct 61 ms 16604 KB Correct.
4 Correct 20 ms 2728 KB Correct.
5 Correct 37 ms 344 KB Correct.
6 Correct 33 ms 600 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 864 KB Correct.
2 Correct 65 ms 1116 KB Correct.
3 Correct 985 ms 24492 KB Correct.
4 Correct 442 ms 7428 KB Correct.
5 Correct 2142 ms 25148 KB Correct.
6 Correct 1439 ms 26812 KB Correct.
7 Correct 437 ms 6932 KB Correct.
8 Correct 343 ms 2816 KB Correct.
9 Correct 377 ms 1704 KB Correct.
10 Correct 337 ms 1772 KB Correct.
11 Correct 366 ms 2684 KB Correct.
12 Correct 381 ms 1864 KB Correct.
13 Correct 399 ms 1724 KB Correct.
14 Correct 478 ms 13200 KB Correct.
15 Correct 441 ms 5364 KB Correct.
16 Correct 409 ms 1864 KB Correct.
17 Correct 414 ms 2004 KB Correct.
18 Correct 413 ms 1852 KB Correct.
19 Correct 895 ms 2840 KB Correct.
20 Correct 23 ms 348 KB Correct.
21 Correct 26 ms 968 KB Correct.
22 Correct 107 ms 3328 KB Correct.

Subtask #8
0.0 / 3.0

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