Submission #921475

#	Time	Username	Problem	Language	Result	Execution time	Memory
921475		Lobo	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	500 ms	90880 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fr first
#define sc second
#define int long long
const int maxn = 1e5+10;
const int inf = 1e18+10;
 
 
int32_t travel_plan(int32_t n, int32_t m, int32_t R[][2], int32_t L[], int32_t k, int32_t P[])
{
	vector<vector<pair<int,int>>> g(n);
	for(int i = 0; i < m; i++) {
		g[R[i][0]].pb(mp(R[i][1],L[i]));
		g[R[i][1]].pb(mp(R[i][0],L[i]));
	}
 
	vector<int> d1(n),d2(n);
	for(int i = 0; i < n; i++) {
		d1[i] = d2[i] = inf;
	}
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
	for(int i = 0; i < k; i++) {
		int v = P[i];
		d1[v] = d2[v] = 0;
		pq.push(mp(0,v));
	}
 	
 	vector<int> mark(n,0);
	while(pq.size()) {
		int u = pq.top().sc;
		int dis2 = pq.top().fr;
		pq.pop();
      	if(mark[u]) continue;
		mark[u] = 1;
 
		for(auto V : g[u]) {
			int v = V.fr;
			int w = V.sc;
			if(d2[v] > d2[u]+w) {
				d2[v] = d2[u]+w;
				if(d2[v] < d1[v]) swap(d2[v],d1[v]);
				if(d2[v] != inf) pq.push(mp(d2[v],v));
			}
		}
	}
 
	return (int32_t) d2[0];
}
 
 

Compilation message (stderr)

crocodile.cpp: In function 'int32_t travel_plan(int32_t, int32_t, int32_t (*)[2], int32_t*, int32_t, int32_t*)':
crocodile.cpp:35:7: warning: unused variable 'dis2' [-Wunused-variable]
   35 |   int dis2 = pq.top().fr;
      |       ^~~~

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