Submission #1248248

#TimeUsernameProblemLanguageResultExecution timeMemory
124824812baaterCrocodile's Underground City (IOI11_crocodile)C++20
0 / 100
0 ms324 KiB
#include "crocodile.h" #include <functional> #include <vector> #include <iostream> #include <queue> using namespace std; typedef long long ll; const int INF = 2E9; 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) { completed = true; for (auto [child, cost] : others) { // cout << "visiting " << child << " from " << num << "\n"; if (chambers[child].completed) continue; if (chambers[child].update_cases(wc+cost)) { 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; } }; 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); } return chambers[0].wc; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...