Submission #363642

#	Time	Username	Problem	Language	Result	Execution time	Memory
363642		David_M	Crocodile's Underground City (IOI11_crocodile)	C++14	89 / 100	651 ms	72924 KiB

crocodile

#include "crocodile.h"
#include<bits/stdc++.h>
#define F first
#define S second
#define ll long long
using namespace std;
const ll INF=1e18, N=100005;

pair<ll, ll> D[N];
vector<pair<int, ll> > v[N];
priority_queue <pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > q;

int travel_plan(int n, int m, int R[][2], int L[], int k, int p[]){
	
	for (int i=0; i<m; i++)
		v[R[i][0]].push_back({R[i][1], L[i]}),
		v[R[i][1]].push_back({R[i][0], L[i]});
	
	for (int i=0; i<n; i++)D[i]={INF, INF};
	for (int i=0; i<k; i++)D[p[i]]={0, 0},q.push({0, p[i]});
	
	while(!q.empty()){
		long long d=q.top().F;
		int x=q.top().S;
		q.pop();
		if(d>D[x].F)continue;
		
		for (auto [y, l] : v[x]){
			if(D[y].F>d+l){
				D[y].F=d+l;
				if(D[y].F<D[y].S)swap(D[y].F, D[y].S);
				if(D[y].F!=INF)q.push({D[y].F, y});
			}
		}
	}
	return D[0].F;
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:28:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   28 |   for (auto [y, l] : v[x]){
      |             ^

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