oj.uz

Submission #983219

# Submission time Handle Problem Language Result Execution time Memory
983219 2024-05-15T09:34:44 Z h_squared Cyberland (APIO23_cyberland) C++17
97 / 100
 856 ms 54864 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,50);
    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 860 KB Correct.
2 Correct 17 ms 800 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1628 KB Correct.
2 Correct 25 ms 1840 KB Correct.
3 Correct 23 ms 1628 KB Correct.
4 Correct 24 ms 1820 KB Correct.
5 Correct 24 ms 1884 KB Correct.
6 Correct 20 ms 4768 KB Correct.
7 Correct 27 ms 4700 KB Correct.
8 Correct 13 ms 8028 KB Correct.
9 Correct 23 ms 1372 KB Correct.
10 Correct 23 ms 1368 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1628 KB Correct.
2 Correct 26 ms 1704 KB Correct.
3 Correct 32 ms 1864 KB Correct.
4 Correct 25 ms 1312 KB Correct.
5 Correct 27 ms 1424 KB Correct.
6 Correct 6 ms 3420 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 22904 KB Correct.
2 Correct 157 ms 1848 KB Correct.
3 Correct 132 ms 1792 KB Correct.
4 Correct 151 ms 2036 KB Correct.
5 Correct 128 ms 1364 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1696 KB Correct.
2 Correct 24 ms 1884 KB Correct.
3 Correct 23 ms 1840 KB Correct.
4 Correct 22 ms 4444 KB Correct.
5 Correct 29 ms 1116 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1704 KB Correct.
2 Correct 22 ms 1692 KB Correct.
3 Correct 59 ms 29780 KB Correct.
4 Correct 19 ms 3224 KB Correct.
5 Correct 23 ms 1372 KB Correct.
6 Correct 26 ms 1752 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 2088 KB Correct.
2 Correct 29 ms 1660 KB Correct.
3 Correct 555 ms 30620 KB Correct.
4 Correct 438 ms 9324 KB Correct.
5 Correct 856 ms 50924 KB Correct.
6 Correct 386 ms 26556 KB Correct.
7 Correct 450 ms 8432 KB Correct.
8 Correct 407 ms 2788 KB Correct.
9 Correct 154 ms 2068 KB Correct.
10 Correct 150 ms 2352 KB Correct.
11 Correct 397 ms 2992 KB Correct.
12 Correct 154 ms 2304 KB Correct.
13 Correct 167 ms 2540 KB Correct.
14 Correct 379 ms 11076 KB Correct.
15 Correct 429 ms 4568 KB Correct.
16 Correct 150 ms 2160 KB Correct.
17 Correct 182 ms 2212 KB Correct.
18 Correct 182 ms 2224 KB Correct.
19 Correct 423 ms 2964 KB Correct.
20 Correct 12 ms 604 KB Correct.
21 Correct 13 ms 924 KB Correct.
22 Correct 24 ms 3276 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 2996 KB Correct.
2 Correct 46 ms 3884 KB Correct.
3 Incorrect 382 ms 54864 KB Wrong Answer.
4 Halted 0 ms 0 KB -