Submission #1270812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270812		cmiuc	Crocodile's Underground City (IOI11_crocodile)	C++20	100 / 100	347 ms	43456 KiB

crocodile

#include <iostream>
#include <vector>
#include <set>

using namespace std;
const int S = 1<<17;
int Min[S][2];
vector<pair<int, int>> nei[S];

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]){
	for (int i=0;i<m;i++){
		nei[r[i][0]].push_back({r[i][1], l[i]});
		nei[r[i][1]].push_back({r[i][0], l[i]});
	}

	for (int i=0;i<=n;i++)
		Min[i][0] = Min[i][1] = 1.1e9;

	set<pair<int,int>> st;
	for (int i=0;i<k;i++){
		Min[p[i]][0] = Min[p[i]][1] = 0;
		st.insert({0, p[i]});
	}

	while (st.size() > 0){
		auto [Mn, u] = *begin(st);
		st.erase(begin(st));

		for (auto [i, w] : nei[u]){
			int cur = Min[i][1];
			if (Min[i][0] > Min[u][1] + w){
				Min[i][1] = Min[i][0];
				Min[i][0] = Min[u][1] + w;
			}
			else if (Min[i][1] > Min[u][1] + w)
				Min[i][1] = Min[u][1] + w;
			
			if (Min[i][1] != cur){
				st.erase({cur, i});
				st.insert({Min[i][1], i});
			}
		}
	}

	return Min[0][1];
}

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