Submission #983044

#	Time	Username	Problem	Language	Result	Execution time	Memory
983044		vjudge1	Cyberland (APIO23_cyberland)	C++17	0 / 100	27 ms	6980 KiB

cyberland

#include <vector>
#include <queue>
#include <limits>
using namespace std;

struct Node {
    int country;
    int time;
    
    Node(int c, int t) : country(c), time(t) {}
    
    bool operator>(const Node& other) const {
        return time > other.time;
    }
};

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    vector<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]});
    }
  
    priority_queue<Node, vector<Node>, greater<Node>> pq;
    vector<int> dist(N, numeric_limits<int>::max());
    
    pq.push(Node(0, 0));
    dist[0] = 0;
    
    int divide_by_2_used = 0;
    
    while (!pq.empty()) {
        Node current = pq.top();
        pq.pop();
        
        int country = current.country;
        int time = current.time;
        if (country == H) return time;
        
        if (divide_by_2_used >= K) continue;
       
        for (auto neighbor : graph[country]) {
            int next_country = neighbor.first;
            int next_time = time + neighbor.second;
            
            if (arr[next_country] == 2) {
                next_time /= 2; // Divide-by-2 ability
                divide_by_2_used++; // Increment divide_by_2 counter
            } else if (arr[next_country] == 0) {
                next_time = 0; // Passing time is 0
            }
            
            if (next_time < dist[next_country]) {
                dist[next_country] = next_time;
                pq.push(Node(next_country, next_time));
            }
        }
    }
    
    return -1;
}

• 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