oj.uz

Submission #488694

# Submission time Handle Problem Language Result Execution time Memory
488694 2021-11-20T05:44:33 Z SansPapyrus683 Crocodile's Underground City (IOI11_crocodile) C++17
46 / 100
 132 ms 262148 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>

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

/**
 * https://oj.uz/problem/view/IOI11_crocodile
 * sample cases are in main()
 * and this function assumes 100% valid input according to the problem
 */
int travel_plan(
    int chamber_num,
    int corridor_num,
    int corridors[][2],
    int times[],
    int exit_num,
    int exits[]
) {
    const int START = 0;

    // i hate arrays, lemme do some processing to so i won't have to use them
    vector<vector<pair<int, int>>> neighbors(chamber_num);
    for (int c = 0; c < corridor_num; c++) {
        int start = corridors[c][0];
        int end = corridors[c][1];
        int time = times[c];
        neighbors[start].push_back({end, time});
        neighbors[end].push_back({start, time});
    }
    
    vector<int> second_best(chamber_num, INT32_MAX);
    for (int e = 0; e < exit_num; e++) {
        second_best[exits[e]] = 0;
    }

    std::function<void(int, int)> fill_second_best;
    fill_second_best = [&] (int at, int prev) {
        if (second_best[at] == 0) {
            return;
        }
        vector<int> costs;
        for (auto [n, n_cost] : neighbors[at]) {
            if (n != prev) {
                fill_second_best(n, at);
                costs.push_back(n_cost + second_best[n]);
            }
        }
        std::sort(costs.begin(), costs.end());
        second_best[at] = costs[1];
    };
    fill_second_best(START, START);
    return second_best[0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 304 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 448 KB Output is correct
8 Correct 1 ms 464 KB Output is correct

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 304 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 448 KB Output is correct
8 Correct 1 ms 464 KB Output is correct
9 Runtime error 132 ms 262148 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 304 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 448 KB Output is correct
8 Correct 1 ms 464 KB Output is correct
9 Runtime error 132 ms 262148 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -