oj.uz

Submission #380671

# Submission time Handle Problem Language Result Execution time Memory
380671 2021-03-22T18:29:41 Z SansPapyrus683 Robot (JOI21_ho_t4) C++17
0 / 100
 513 ms 43516 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <climits>

using std::cout;
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<vector<pair<int, int>>> neighbors;
    for (const std::unordered_map<int, vector<pair<int, int>>>& r_list : color_neighbors) {
        vector<pair<int, int>> rn_adj;
        for (auto const& [c, n] : r_list) {
            if (n.size() == 1) {
                rn_adj.push_back({n[0].first, 0});
            } else {
                rn_adj.insert(rn_adj.end(), n.begin(), n.end());
            }
        }
        neighbors.push_back(rn_adj);
    }

    vector<long long> min_cost(crossing_num, LLONG_MAX);
    min_cost[0] = 0;
    std::priority_queue<pair<long long, int>> frontier;
    frontier.push({0, 0});
    while (!frontier.empty()) {
        int curr = frontier.top().second;
        frontier.pop();
        for (auto const& [n, nc] : neighbors[curr]) {
            int new_cost = min_cost[curr] + nc;
            if (new_cost < min_cost[n]) {
                min_cost[n] = new_cost;
                frontier.push({-new_cost, n});
            }
        }
    }
    cout << (min_cost[crossing_num - 1] == LLONG_MAX ? -1 : min_cost[crossing_num - 1]) << endl;
}

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Incorrect 2 ms 364 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 13232 KB Output is correct
2 Correct 65 ms 6824 KB Output is correct
3 Correct 241 ms 13348 KB Output is correct
4 Correct 98 ms 9508 KB Output is correct
5 Incorrect 513 ms 43516 KB Output isn't correct
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 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Incorrect 2 ms 364 KB Output isn't correct
8 Halted 0 ms 0 KB -