Submission #988220

#	Time	Username	Problem	Language	Result	Execution time	Memory
988220		BF001	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	420 ms	76596 KiB

crocodile

#include <bits/stdc++.h>
using namespace std;

#define NN 100005
#define oo 1e18
#define fi first
#define se second

typedef pair<long long, long long> ii;

long long n, m, k, d1[NN], d2[NN];
vector<long long> sr;
vector<ii> adj[NN];

long long ditra(){
	for (long long i = 0; i <= n; i++) d1[i] = d2[i] = oo;
	priority_queue<ii, vector<ii>, greater<ii>> q;
	for (auto x : sr){
		d2[x] = d1[x] = 0;
		q.push({0, x});
	}
	while (!q.empty()){
		long long u = q.top().se;
		long long du = q.top().fi;
		q.pop();
		if (du != d2[u]) continue;
		for (auto x : adj[u]){
			long long v = x.fi;
			long long dv = x.se;
			if (du + dv < d1[v]){
				if (d1[v] != oo && d1[v] != d2[v]){
					q.push({d1[v], v});
				}
				d2[v] = d1[v];
				d1[v] = du + dv;
			}
			else if (du + dv < d2[v]){
				d2[v] = du + dv;
				q.push({d2[v], v});
			}
		}
	}
	return d2[0];
}

long long travel_plan(int  N, int M , int R[][2], int L[], int k, int p[]){
	n = N;
	m = M;
	for (long long i = 0; i < m; i++){
		long long a = R[i][0], b = R[i][1], c = L[i];
		adj[a].push_back({b, c});
		adj[b].push_back({a, c}); 
	}
	for (long long i = 0; i < k; i++){
		sr.push_back(p[i]);
	}
	return ditra();
}

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