Submission #1248244

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248244		12baater	Crocodile's Underground City (IOI11_crocodile)	C++20	0 / 100	0 ms	320 KiB

crocodile

#include "crocodile.h"
#include <functional>
#include <vector>
#include <iostream>
#include <queue>

using namespace std;
typedef long long ll;

const bool DEBUG = 0;
const ll INF = 1E15;

struct chamber {
    int num;
    bool completed = false;
    bool is_exit = false;
    vector<pair<int,int>> others;
    ll wc = INF, bc = INF;

    void update_others(vector<chamber>& chambers, priority_queue<chamber, vector<chamber>, greater<>>& current_exits) {
        if (num == 0) return;
        for (auto [child, cost] : others) {
            // cout << "visiting " << child << " from " << num << "\n";
            if (chambers[child].completed) continue;
            if (chambers[child].update_cases(wc+cost)) {
                if (chambers[child].wc != INF && chambers[child].bc != INF)
                    current_exits.push(chambers[child]);
            }
        }
    }

    bool update_cases(ll val) {
        if (wc == INF) {
            wc = val;
            if (wc < bc) swap(wc,bc);
            return (wc != INF);
        }
        if (val > wc) return false;
        wc = val;
        if (wc < bc) swap(wc,bc);
        return true;
    }

    bool operator<(const chamber& other_chamber) const {
        return wc < other_chamber.wc;
    }

    bool operator>(const chamber& other_chamber) const {
        return wc > other_chamber.wc;
    }

    void print() {
        printf("Number %d, wc %lld, bc %lld\n", num, wc, bc);
    }
};



int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    vector<chamber> chambers(N);
    priority_queue<chamber, vector<chamber>, greater<>> current_exits;

    for (int i = 0; i < N; i++) {
        chambers[i].num = i;
    }

    for (int i = 0; i < M; i++) {
        int a = R[i][0];
        int b = R[i][1];
        chambers[a].others.emplace_back(b, L[i]);
        chambers[b].others.emplace_back(a, L[i]);
    }

    for (int i = 0; i < K; i++) {
        chambers[P[i]].is_exit = true;
        chambers[P[i]].completed = true;
        chambers[P[i]].wc = 0;
        chambers[P[i]].bc = 0;
        current_exits.push(chambers[P[i]]);
    }

    while (!current_exits.empty()) {
        int currentChamber = current_exits.top().num; current_exits.pop();
        // cout << "visited " << currentChamber << "\n";
        chambers[currentChamber].update_others(chambers, current_exits);
    }

    // if (DEBUG) {
    //     for (auto a : chambers) {
    //         a.print();
    //     }
    // }

    return static_cast<int>(chambers[0].wc);
}

• Subtask 1: 0 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11