Submission #1200552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200552		PlayVoltz	Crocodile's Underground City (IOI11_crocodile)	C++20	89 / 100	292 ms	46680 KiB

crocodile

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

#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int travel_plan(int n, int m, int R[][2], int L[], int k, int vect[]){
	vector<vector<pii> > graph(n);
	for (int i=0; i<m; ++i){
		graph[R[i][0]].pb(mp(R[i][1], L[i]));
		graph[R[i][1]].pb(mp(R[i][0], L[i]));
	}
	vector<vector<int> > dj(n, vector<int>(2, INT_MAX/2));
	priority_queue<pii, vector<pii>, greater<pii> > pq;
	for (int i=0; i<k; ++i){
		dj[vect[i]][0]=dj[vect[i]][1]=0;
		pq.push(mp(0, vect[i]));
	}
	while (pq.size()){
		int d=pq.top().fi, node=pq.top().se;
		pq.pop();
		if (d>dj[node][1])continue;
		for (auto num:graph[node]){
			if (num.se+d<dj[num.fi][0]){
				if (dj[num.fi][0]!=INT_MAX/2)pq.push(mp(dj[num.fi][0], num.fi));
				dj[num.fi][1]=dj[num.fi][0];
				dj[num.fi][0]=num.se+d;
			}
			else if (num.se+d<dj[num.fi][1]){
				dj[num.fi][1]=num.se+d;
				pq.push(mp(dj[num.fi][1], num.fi));
			}
		}
	}
	return dj[0][1];
}

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