oj.uz

Submission #983215

# Submission time Handle Problem Language Result Execution time Memory
983215 2024-05-15T09:32:41 Z h_squared Cyberland (APIO23_cyberland) C++17
97 / 100
 1478 ms 2097152 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]});
    }
    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][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 860 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 860 KB Correct.
2 Correct 27 ms 1884 KB Correct.
3 Correct 24 ms 1628 KB Correct.
4 Correct 24 ms 1832 KB Correct.
5 Correct 24 ms 1688 KB Correct.
6 Correct 20 ms 4768 KB Correct.
7 Correct 27 ms 4700 KB Correct.
8 Correct 13 ms 8020 KB Correct.
9 Correct 25 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 25 ms 600 KB Correct.
2 Correct 25 ms 1704 KB Correct.
3 Correct 23 ms 1624 KB Correct.
4 Correct 25 ms 1452 KB Correct.
5 Correct 24 ms 1480 KB Correct.
6 Correct 6 ms 3416 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 21420 KB Correct.
2 Correct 417 ms 2112 KB Correct.
3 Correct 360 ms 1808 KB Correct.
4 Correct 394 ms 1944 KB Correct.
5 Correct 264 ms 1420 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 852 KB Correct.
2 Correct 24 ms 1808 KB Correct.
3 Correct 23 ms 1836 KB Correct.
4 Correct 21 ms 4344 KB Correct.
5 Correct 20 ms 1372 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 860 KB Correct.
2 Correct 21 ms 1652 KB Correct.
3 Correct 53 ms 29776 KB Correct.
4 Correct 20 ms 3276 KB Correct.
5 Correct 23 ms 1440 KB Correct.
6 Correct 23 ms 1716 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 1432 KB Correct.
2 Correct 28 ms 1668 KB Correct.
3 Correct 1478 ms 29780 KB Correct.
4 Correct 1069 ms 9288 KB Correct.
5 Correct 943 ms 52052 KB Correct.
6 Correct 303 ms 26916 KB Correct.
7 Correct 1085 ms 8332 KB Correct.
8 Correct 917 ms 3156 KB Correct.
9 Correct 223 ms 2348 KB Correct.
10 Correct 242 ms 2304 KB Correct.
11 Correct 832 ms 2672 KB Correct.
12 Correct 240 ms 2228 KB Correct.
13 Correct 234 ms 2664 KB Correct.
14 Correct 867 ms 10760 KB Correct.
15 Correct 1161 ms 4916 KB Correct.
16 Correct 223 ms 2460 KB Correct.
17 Correct 277 ms 2292 KB Correct.
18 Correct 283 ms 2416 KB Correct.
19 Correct 885 ms 3728 KB Correct.
20 Correct 16 ms 604 KB Correct.
21 Correct 20 ms 1116 KB Correct.
22 Correct 20 ms 2260 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 1082 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -