oj.uz

Submission #983230

# Submission time Handle Problem Language Result Execution time Memory
983230 2024-05-15T09:38:15 Z h_squared Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 168160 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,100);
    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 856 KB Correct.
2 Correct 17 ms 520 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 860 KB Correct.
2 Correct 23 ms 860 KB Correct.
3 Correct 22 ms 840 KB Correct.
4 Correct 31 ms 808 KB Correct.
5 Correct 24 ms 848 KB Correct.
6 Correct 20 ms 3996 KB Correct.
7 Correct 26 ms 3932 KB Correct.
8 Correct 13 ms 7516 KB Correct.
9 Correct 23 ms 348 KB Correct.
10 Correct 22 ms 564 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 852 KB Correct.
2 Correct 25 ms 832 KB Correct.
3 Correct 23 ms 852 KB Correct.
4 Correct 25 ms 344 KB Correct.
5 Correct 26 ms 344 KB Correct.
6 Correct 6 ms 3416 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 21508 KB Correct.
2 Correct 166 ms 860 KB Correct.
3 Correct 131 ms 840 KB Correct.
4 Correct 135 ms 828 KB Correct.
5 Correct 130 ms 576 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 812 KB Correct.
2 Correct 23 ms 600 KB Correct.
3 Correct 23 ms 796 KB Correct.
4 Correct 21 ms 3676 KB Correct.
5 Correct 20 ms 344 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 860 KB Correct.
2 Correct 21 ms 776 KB Correct.
3 Correct 47 ms 27980 KB Correct.
4 Correct 16 ms 2504 KB Correct.
5 Correct 24 ms 348 KB Correct.
6 Correct 23 ms 812 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 1144 KB Correct.
2 Correct 22 ms 1676 KB Correct.
3 Correct 529 ms 28248 KB Correct.
4 Correct 426 ms 7168 KB Correct.
5 Correct 815 ms 49324 KB Correct.
6 Correct 348 ms 24000 KB Correct.
7 Correct 427 ms 7284 KB Correct.
8 Correct 412 ms 1744 KB Correct.
9 Correct 151 ms 1716 KB Correct.
10 Correct 152 ms 1480 KB Correct.
11 Correct 388 ms 980 KB Correct.
12 Correct 154 ms 1388 KB Correct.
13 Correct 168 ms 1440 KB Correct.
14 Correct 356 ms 9572 KB Correct.
15 Correct 422 ms 2816 KB Correct.
16 Correct 144 ms 1368 KB Correct.
17 Correct 180 ms 1172 KB Correct.
18 Correct 180 ms 1380 KB Correct.
19 Correct 421 ms 1340 KB Correct.
20 Correct 12 ms 604 KB Correct.
21 Correct 16 ms 924 KB Correct.
22 Correct 23 ms 3280 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 818 ms 4340 KB Correct.
2 Correct 107 ms 7828 KB Correct.
3 Correct 643 ms 91272 KB Correct.
4 Correct 1131 ms 5668 KB Correct.
5 Execution timed out 3005 ms 168160 KB Time limit exceeded
6 Halted 0 ms 0 KB -