oj.uz

Submission #983227

# Submission time Handle Problem Language Result Execution time Memory
983227 2024-05-15T09:36:58 Z h_squared Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 182948 KB 
#include "cyberland.h"
#include<bits/stdc++.h>
#include <cmath>
using namespace std;


struct node{
    int u,k;double cost;
};
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
    
    vector<vector<pair<int,int>>>adj(N);
    for(int i=0;i<M;i++){
        adj[x[i]].push_back({y[i],c[i]});
        adj[y[i]].push_back({x[i],c[i]});
    }
    K=min(K,150);
    vector<vector<double>>d(N,vector<double>(K+1,1e18));
    d[0][0]=0;
    auto cmp=[](node& a,node &b){return a.cost>b.cost;};
    priority_queue<node,vector<node>,decltype(cmp)>pq(cmp);
    pq.push({0,0,0});
    double ans=1e18;
    while(!pq.empty()){
        auto [u,k,cost]=pq.top();pq.pop();
        if(d[u][k]<cost)continue;
        if(u==H){
            ans=min(ans,cost);
            continue;
        }
        for(auto [v,w]:adj[u]){
            double now=cost+w;
            if(arr[v]==0){
                now=0;
                if(now<d[v][0]){
                    d[v][0]=now;
                    pq.push({v,0,now});
                }
            }
            else{
                if(now<d[v][k]){
                    d[v][k]=now;
                    pq.push({v,k,now});
                }
                if(arr[v]==2 && k<K){
                    now=now/2;
                    if(now<d[v][k+1]){
                        d[v][k+1]=now;
                        pq.push({v,k+1,now});
                    }
                }
            }
        }
    }
    if(ans==1e18)return -1;
    else return ans;

}

Subtask #1
5.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 860 KB Correct.
2 Correct 24 ms 860 KB Correct.
3 Correct 23 ms 820 KB Correct.
4 Correct 24 ms 808 KB Correct.
5 Correct 24 ms 828 KB Correct.
6 Correct 20 ms 4000 KB Correct.
7 Correct 26 ms 3800 KB Correct.
8 Correct 18 ms 7532 KB Correct.
9 Correct 24 ms 348 KB Correct.
10 Correct 22 ms 348 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 604 KB Correct.
2 Correct 29 ms 760 KB Correct.
3 Correct 23 ms 860 KB Correct.
4 Correct 25 ms 556 KB Correct.
5 Correct 25 ms 552 KB Correct.
6 Correct 6 ms 3416 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 21340 KB Correct.
2 Correct 158 ms 848 KB Correct.
3 Correct 138 ms 920 KB Correct.
4 Correct 139 ms 936 KB Correct.
5 Correct 139 ms 584 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 808 KB Correct.
2 Correct 23 ms 600 KB Correct.
3 Correct 34 ms 816 KB Correct.
4 Correct 29 ms 3848 KB Correct.
5 Correct 23 ms 788 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 772 KB Correct.
2 Correct 21 ms 904 KB Correct.
3 Correct 53 ms 27988 KB Correct.
4 Correct 17 ms 2572 KB Correct.
5 Correct 23 ms 348 KB Correct.
6 Correct 23 ms 756 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 1080 KB Correct.
2 Correct 22 ms 1664 KB Correct.
3 Correct 511 ms 28320 KB Correct.
4 Correct 426 ms 7168 KB Correct.
5 Correct 751 ms 48880 KB Correct.
6 Correct 333 ms 25024 KB Correct.
7 Correct 426 ms 7272 KB Correct.
8 Correct 410 ms 1640 KB Correct.
9 Correct 149 ms 1496 KB Correct.
10 Correct 151 ms 1316 KB Correct.
11 Correct 389 ms 1000 KB Correct.
12 Correct 155 ms 1496 KB Correct.
13 Correct 168 ms 1480 KB Correct.
14 Correct 354 ms 9552 KB Correct.
15 Correct 421 ms 2928 KB Correct.
16 Correct 145 ms 1304 KB Correct.
17 Correct 175 ms 1184 KB Correct.
18 Correct 177 ms 1376 KB Correct.
19 Correct 418 ms 1232 KB Correct.
20 Correct 12 ms 604 KB Correct.
21 Correct 12 ms 924 KB Correct.
22 Correct 23 ms 3276 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1057 ms 4796 KB Correct.
2 Correct 127 ms 8820 KB Correct.
3 Correct 616 ms 91472 KB Correct.
4 Correct 1249 ms 8356 KB Correct.
5 Execution timed out 3063 ms 182948 KB Time limit exceeded
6 Halted 0 ms 0 KB -