Submission #488694

#	Time	Username	Problem	Language	Result	Execution time	Memory
488694		SansPapyrus683	Crocodile's Underground City (IOI11_crocodile)	C++17	46 / 100	132 ms	262148 KiB

crocodile

#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 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11