oj.uz

Submission #983238

# Submission time Handle Problem Language Result Execution time Memory
983238 2024-05-15T09:41:17 Z h_squared Cyberland (APIO23_cyberland) C++17
44 / 100
 123 ms 13168 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>(2,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 pw=1;
    for(int i=0;i<K;i++)pw/=2;
    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==0){
                    now*=pw;
                    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
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 856 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1372 KB Correct.
2 Correct 24 ms 1492 KB Correct.
3 Correct 23 ms 1496 KB Correct.
4 Correct 23 ms 1500 KB Correct.
5 Correct 24 ms 1620 KB Correct.
6 Correct 19 ms 2788 KB Correct.
7 Correct 28 ms 2716 KB Correct.
8 Correct 11 ms 3676 KB Correct.
9 Correct 23 ms 1372 KB Correct.
10 Correct 23 ms 1404 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1616 KB Correct.
2 Correct 25 ms 1600 KB Correct.
3 Correct 27 ms 1544 KB Correct.
4 Correct 25 ms 1420 KB Correct.
5 Correct 25 ms 1368 KB Correct.
6 Correct 5 ms 1624 KB Correct.

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 10052 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1372 KB Correct.
2 Correct 23 ms 1472 KB Correct.
3 Correct 26 ms 1884 KB Correct.
4 Correct 21 ms 2424 KB Correct.
5 Correct 21 ms 1280 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1628 KB Correct.
2 Correct 21 ms 1368 KB Correct.
3 Correct 36 ms 13168 KB Correct.
4 Correct 14 ms 2016 KB Correct.
5 Correct 23 ms 1368 KB Correct.
6 Correct 22 ms 1368 KB Correct.

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 1628 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 123 ms 1364 KB Wrong Answer.
2 Halted 0 ms 0 KB -