Submission #250474

#	Time	Username	Problem	Language	Result	Execution time	Memory
250474		kostia244	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	809 ms	62188 KiB

crocodile

#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1<<17;
vector<array<int, 2>> g[maxn];
array<int, 2> dist[maxn];
priority_queue<array<int, 2>> pq;
void relax(int u, int d) {
	if(d > 1<<30) return;
	int old = dist[u][1];
	if(dist[u][0] > d) {
		dist[u][1] = dist[u][0];
		dist[u][0] = d;
	} else if(dist[u][1] > d) {
		dist[u][1] = d;
	}
	if(dist[u][1] < old)
		pq.push({-dist[u][1], u});
}
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
	fill(begin(dist), end(dist), array<int, 2>{1<<30, 1<<30});
	for(int i = 0; i < k; i++) {
		relax(p[i], 0);
		relax(p[i], 0);
	}
	for(int i = 0; i < m; i++) {
		g[r[i][0]].push_back({r[i][1], l[i]});
		g[r[i][1]].push_back({r[i][0], l[i]});
	}
	while(!pq.empty()) {
		auto [cst, u] = pq.top();
		pq.pop();
		cst *= -1;
		if(cst > dist[u][1]) continue;
		for(auto [i, w] : g[u])
			relax(i, cst + w);
	}
	return dist[0][1];
}

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