oj.uz

Submission #985441

# Submission time Handle Problem Language Result Execution time Memory
985441 2024-05-17T20:27:15 Z oviyan_gandhi Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 28380 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#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, 67);
    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 18 ms 588 KB Correct.
2 Correct 19 ms 600 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 600 KB Correct.
2 Correct 31 ms 652 KB Correct.
3 Correct 27 ms 604 KB Correct.
4 Correct 33 ms 600 KB Correct.
5 Correct 29 ms 848 KB Correct.
6 Correct 27 ms 2400 KB Correct.
7 Correct 34 ms 2408 KB Correct.
8 Correct 14 ms 4700 KB Correct.
9 Correct 28 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 700 KB Correct.
2 Correct 32 ms 604 KB Correct.
3 Correct 30 ms 604 KB Correct.
4 Correct 31 ms 780 KB Correct.
5 Correct 31 ms 540 KB Correct.
6 Correct 7 ms 2388 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 14044 KB Correct.
2 Correct 238 ms 600 KB Correct.
3 Correct 212 ms 932 KB Correct.
4 Correct 226 ms 600 KB Correct.
5 Correct 141 ms 768 KB Correct.

Subtask #5
7.0 / 7.0

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

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 604 KB Correct.
2 Correct 26 ms 604 KB Correct.
3 Correct 43 ms 17020 KB Correct.
4 Correct 28 ms 2624 KB Correct.
5 Correct 28 ms 344 KB Correct.
6 Correct 29 ms 768 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 391 ms 624 KB Correct.
2 Correct 65 ms 1356 KB Correct.
3 Correct 761 ms 21772 KB Correct.
4 Correct 356 ms 4916 KB Correct.
5 Correct 1491 ms 22240 KB Correct.
6 Correct 1253 ms 24516 KB Correct.
7 Correct 356 ms 5692 KB Correct.
8 Correct 303 ms 1136 KB Correct.
9 Correct 323 ms 852 KB Correct.
10 Correct 332 ms 800 KB Correct.
11 Correct 300 ms 848 KB Correct.
12 Correct 344 ms 948 KB Correct.
13 Correct 373 ms 848 KB Correct.
14 Correct 386 ms 11440 KB Correct.
15 Correct 337 ms 3004 KB Correct.
16 Correct 338 ms 848 KB Correct.
17 Correct 377 ms 852 KB Correct.
18 Correct 369 ms 744 KB Correct.
19 Correct 786 ms 796 KB Correct.
20 Correct 21 ms 344 KB Correct.
21 Correct 27 ms 664 KB Correct.
22 Correct 100 ms 3328 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 830 ms 624 KB Correct.
2 Correct 138 ms 1116 KB Correct.
3 Correct 335 ms 28380 KB Correct.
4 Correct 416 ms 1848 KB Correct.
5 Execution timed out 3060 ms 20932 KB Time limit exceeded
6 Halted 0 ms 0 KB -