oj.uz

Submission #985439

# Submission time Handle Problem Language Result Execution time Memory
985439 2024-05-17T20:22:31 Z oviyan_gandhi Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 35792 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) {
  	K = min(K, 69);
    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 856 KB Correct.
2 Correct 19 ms 860 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 600 KB Correct.
2 Correct 29 ms 688 KB Correct.
3 Correct 28 ms 604 KB Correct.
4 Correct 29 ms 604 KB Correct.
5 Correct 29 ms 600 KB Correct.
6 Correct 25 ms 2404 KB Correct.
7 Correct 34 ms 2664 KB Correct.
8 Correct 15 ms 4696 KB Correct.
9 Correct 27 ms 348 KB Correct.
10 Correct 26 ms 344 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 604 KB Correct.
2 Correct 33 ms 1628 KB Correct.
3 Correct 31 ms 852 KB Correct.
4 Correct 31 ms 1372 KB Correct.
5 Correct 31 ms 1368 KB Correct.
6 Correct 8 ms 2588 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 14720 KB Correct.
2 Correct 253 ms 1980 KB Correct.
3 Correct 220 ms 1712 KB Correct.
4 Correct 236 ms 1780 KB Correct.
5 Correct 157 ms 1400 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 600 KB Correct.
2 Correct 30 ms 604 KB Correct.
3 Correct 29 ms 788 KB Correct.
4 Correct 30 ms 2972 KB Correct.
5 Correct 24 ms 344 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 860 KB Correct.
2 Correct 26 ms 1408 KB Correct.
3 Correct 44 ms 18512 KB Correct.
4 Correct 21 ms 3240 KB Correct.
5 Correct 29 ms 1288 KB Correct.
6 Correct 29 ms 1660 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 409 ms 1344 KB Correct.
2 Correct 63 ms 1368 KB Correct.
3 Correct 780 ms 24552 KB Correct.
4 Correct 387 ms 7200 KB Correct.
5 Correct 1580 ms 25540 KB Correct.
6 Correct 1285 ms 25792 KB Correct.
7 Correct 383 ms 6864 KB Correct.
8 Correct 327 ms 2868 KB Correct.
9 Correct 339 ms 1876 KB Correct.
10 Correct 332 ms 1616 KB Correct.
11 Correct 318 ms 2644 KB Correct.
12 Correct 339 ms 2100 KB Correct.
13 Correct 364 ms 1620 KB Correct.
14 Correct 377 ms 13352 KB Correct.
15 Correct 353 ms 4988 KB Correct.
16 Correct 350 ms 1652 KB Correct.
17 Correct 390 ms 1928 KB Correct.
18 Correct 382 ms 1628 KB Correct.
19 Correct 824 ms 2712 KB Correct.
20 Correct 21 ms 604 KB Correct.
21 Correct 23 ms 764 KB Correct.
22 Correct 103 ms 3588 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 893 ms 852 KB Correct.
2 Correct 145 ms 1116 KB Correct.
3 Correct 407 ms 35792 KB Correct.
4 Correct 464 ms 3972 KB Correct.
5 Execution timed out 3039 ms 23992 KB Time limit exceeded
6 Halted 0 ms 0 KB -