Submission #1183795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183795		Aviansh	Cyberland (APIO23_cyberland)	C++20	97 / 100	3099 ms	80672 KiB

cyberland

#include "cyberland.h"

#include <bits/stdc++.h>

using namespace std;

void dfs(int st, vector<array<int,2>>(&g)[], bool vis[], int h){
    vis[st]=1;
    if(st==h)
        return;
    for(array<int,2>e:g[st]){
        if(vis[e[0]])
            continue;
        dfs(e[0],g,vis,h);
    }
}

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) {
    const int mxk = 70;
    k=min(k,mxk-2);
    double tim[n][mxk];
    for(int i = 0;i<n;i++){
        for(int j = 0;j<mxk;j++){
            tim[i][j]=2e18;
        }
    }
    vector<array<int,2>>g[n];
    for(int i = 0;i<m;i++){
        g[x[i]].push_back({y[i],c[i]});
        g[y[i]].push_back({x[i],c[i]});
    }
    bool vis[n];
    fill(vis,vis+n,0);
    dfs(0,g,vis,h);
    set<tuple<double,int,int>>pq;
    pq.insert({0,0,0});
    for(int i = 0;i<n;i++){
        if(vis[i]&&arr[i]==0){
            pq.insert({0,i,0});
        }
    }
    tim[0][0]=0;
    //{time,index,usedk}
    while(!pq.empty()){
        tuple<double,int,int>curr = *(pq.begin());
        pq.erase(pq.begin());
        if(tim[get<1>(curr)][get<2>(curr)]!=get<0>(curr)){
            continue;
        }
        if(get<1>(curr)==h)
            continue;
        for(array<int,2>e:g[get<1>(curr)]){
            if(arr[get<1>(curr)]==0){
                if(tim[e[0]][0]>e[1]){
                    pq.erase({tim[e[0]][0],e[0],0});
                    pq.insert({e[1],e[0],0});
                    tim[e[0]][0]=e[1];

                }
            }
            else {
                if(tim[e[0]][get<2>(curr)]>get<0>(curr)+e[1]){
                    pq.erase({tim[e[0]][get<2>(curr)],e[0],get<2>(curr)});
                    pq.insert({get<0>(curr)+e[1],e[0],get<2>(curr)});
                    tim[e[0]][get<2>(curr)]=get<0>(curr)+e[1];
                }
                if(arr[get<1>(curr)]==2&&get<2>(curr)<k){
                    if(tim[e[0]][get<2>(curr)+1]>(get<0>(curr)/2)+e[1]){
                        pq.erase({tim[e[0]][get<2>(curr)+1],e[0],get<2>(curr)+1});
                        pq.insert({(get<0>(curr)/2)+e[1],e[0],get<2>(curr)+1});
                        tim[e[0]][get<2>(curr)+1]=(get<0>(curr)/2)+e[1];
                    }
                }
            }
        }
    }
    double ans = 2e18;
    for(int i = 0;i<mxk;i++){
        ans=min(ans,tim[h][i]);
    }
    if(ans==2e18){
        return -1;
    }
    else{
        return ans;
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 29 / 29
• Subtask 8: 0 / 3