oj.uz

Submission #990693

# Submission time Handle Problem Language Result Execution time Memory
990693 2024-05-31T03:30:59 Z Ibrohim0704 Cyberland (APIO23_cyberland) C++17
0 / 100
 834 ms 2097152 KB 
#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; // Already visited this state with a better passing time
        }
        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; // Cannot reach Cyberland
}

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 352 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 135 ms 240140 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 834 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 30 ms 49608 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 102 ms 171420 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 41 ms 56656 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 740 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -