Submission #964055

#	Time	Username	Problem	Language	Result	Execution time	Memory
964055		pragmatist	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	593 ms	49104 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int N = (int)1e5+7;
const long long INF = (long long)1e18+7;
 
vector<pair<int, int> > g[N];
int n, m;
long long d1[N], d2[N];
 
int travel_plan(int _N, int _M, int _R[][2], int _L[], int _K, int _P[]) {
	n = _N;
	m = _M;
	for(int i = 0; i < m; ++i) {
		int u = _R[i][0], v = _R[i][1], w = _L[i];
		u++;
		v++;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	for(int i = 1; i <= n; ++i) {
		d1[i] = d2[i] = INF;
	}

	set<pair<long long, int> > q;
	for(int i = 0; i < _K; ++i) {
		int v = _P[i]+1;
		d1[v]=d2[v]=0;
		q.insert({0, v});
	}
	while(!q.empty()) {
		int v = q.begin()->second;
	    q.erase(q.begin());

		for(auto [to, w] : g[v]) {
			if(d2[v]+w<d1[to]) {
			    q.erase({d2[to], to});
				d2[to]=d1[to];
				d1[to]=d2[v]+w;
				q.insert({d2[to], to});				
			} else {    
				if(d2[v]+w<d2[to]) {
				    q.erase({d2[to], to});
					d2[to]=d2[v]+w;
					q.insert({d2[to], to});				
				}
			}
		}
	}
	return d2[1];
}

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