Submission #990692

#	Time	Username	Problem	Language	Result	Execution time	Memory
990692		Ibrohim0704	Cyberland (APIO23_cyberland)	C++17	0 / 100	929 ms	2097152 KiB

cyberland

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

struct Node {
    int country;
    int passing_time;
    int divide_count;

    Node(int c, int t, int d) : country(c), passing_time(t), divide_count(d) {}
    
    bool operator<(const Node& other) const {
        return passing_time > other.passing_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> pq;
    pq.push(Node(0, 0, 0));

    vector<vector<vector<int>>> dp(N, vector<vector<int>>(K + 1, vector<int>(N, INT_MAX)));

    while (!pq.empty()) {
        Node curr = pq.top();
        pq.pop();

        if (curr.country == H) {
            return curr.passing_time;
        }

        if (dp[curr.country][curr.divide_count][curr.passing_time] != INT_MAX) {
            continue;
        }
        dp[curr.country][curr.divide_count][curr.passing_time] = curr.passing_time;

        for (auto& neighbor : graph[curr.country]) {
            int next_country = neighbor.first;
            int next_time = curr.passing_time + neighbor.second;
            int next_divide_count = curr.divide_count;

            if (arr[next_country] == 2 && next_divide_count < K) {
                next_time /= 2;
                next_divide_count++;
            }

            pq.push(Node(next_country, next_time, next_divide_count));
        }
    }

    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