oj.uz

Submission #381316

# Submission time Handle Problem Language Result Execution time Memory
381316 2021-03-25T05:07:28 Z SansPapyrus683 Robot (JOI21_ho_t4) C++17
0 / 100
 3000 ms 54268 KB 
#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
#include <unordered_map>
#include <climits>

using std::cout;
using std::get;
using std::endl;
using std::vector;
using std::pair;

// https://oj.uz/problem/view/JOI21_ho_t4 (input ommitted due to length)
int main() {
    int crossing_num;
    int road_num;
    std::cin >> crossing_num >> road_num;
    vector<std::unordered_map<int, vector<pair<int, int>>>> color_neighbors(crossing_num);
    for (int r = 0; r < road_num; r++) {
        int from;
        int to;
        int color;
        int change_cost;
        std::cin >> from >> to >> color >> change_cost;
        color_neighbors[--from][color].push_back({--to, change_cost});
        color_neighbors[to][color].push_back({from, change_cost});
    }

    vector<std::unordered_map<int, long long>> min_cost(crossing_num);
    min_cost[0][-1] = 0;
    std::priority_queue<pair<long long, pair<int, int>>> frontier;
    frontier.push({0, {0, -1}});
    while (!frontier.empty()) {
        pair<int, int> curr = frontier.top().second;
        long long curr_cost = min_cost[curr.first][curr.second];
        if (-frontier.top().first != curr_cost) {
            continue;
        }
        if (curr.first == crossing_num - 1) {
            cout << curr_cost << endl;
            goto end;
        }
        frontier.pop();
        for (auto const& [c, n_list] : color_neighbors[curr.first]) {
            bool need_change = n_list.size() > (1 + (c == curr.second));
            for (auto const& [n, nc] : n_list) {
                long long new_cost = curr_cost + nc;
                if (min_cost[n].find(c) == min_cost[n].end() || new_cost < min_cost[n][c]) {
                    min_cost[n][c] = new_cost;
                    frontier.push({-new_cost, {n, c}});
                }
                if (need_change) {
                    continue;
                }
                if (min_cost[n].find(-1) == min_cost[n].end() || curr_cost < min_cost[n][-1]) {
                    min_cost[n][-1] = curr_cost;
                    frontier.push({-curr_cost, {n, -1}});
                }
            }
        }
    }
    cout << -1 << endl;
    end:;
}

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Execution timed out 3065 ms 364 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 15712 KB Output is correct
2 Correct 100 ms 8804 KB Output is correct
3 Correct 215 ms 11372 KB Output is correct
4 Correct 108 ms 10724 KB Output is correct
5 Execution timed out 3074 ms 54268 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Execution timed out 3065 ms 364 KB Time limit exceeded
6 Halted 0 ms 0 KB -