Submission #896549

#	Time	Username	Problem	Language	Result	Execution time	Memory
896549		NotLinux	Cyberland (APIO23_cyberland)	C++17	0 / 100	916 ms	22668 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair < double , pair < int , int > > VAR;

const int MAXK = 31;

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) {
    bitset < 31 > vis[n];
    for(int i = 0;i<n;i++){
        vis[i] = 0;
    }
    priority_queue < VAR > pq;//dist , node , how much k used
    pq.push({0,{0,0}});
    for(int i = 0;i<n;i++){
        if(arr[i] == 0){
            pq.push({0,{i,0}});
        }
    }
    vector < pair < int , int > > graph[n];
    for(int i = 0;i<m;i++){
        graph[x[i]].push_back({y[i] , c[i]});
        graph[y[i]].push_back({x[i] , c[i]});
    }
    double ans = -1;
    while(pq.size()){
        VAR tmp = pq.top();
        pq.pop();
        if(vis[tmp.second.first][tmp.second.second])continue;
        //cout << "pq : " << tmp.first << " " << tmp.second.first << " " << tmp.second.second << endl;
        vis[tmp.second.first][tmp.second.second] = 1;
        if(tmp.second.first == (n-1)){
            if(ans == -1 or ans < tmp.first){
                ans = tmp.first;
            }
        }
        if(tmp.second.first < (n-1)){
            //use an ability in here
            if(arr[tmp.second.first] == 2 and tmp.second.second < k){
                pq.push({tmp.first / 2 , {tmp.second.first , tmp.second.second + 1}});
            }
            //go to another vertex
            for(auto itr : graph[tmp.second.first]){
                pq.push({tmp.first - itr.second , {itr.first , tmp.second.second}});
            }
        }
    }
    return -ans;
}

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