Submission #798412

#	Time	Username	Problem	Language	Result	Execution time	Memory
798412		Theo830	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	621 ms	72348 KiB

crocodile

#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(int i = a;i < b;i++)
#define ll int
#define pb push_back
#define F first
#define S second
#define ii pair<ll,ll>
vector<vector<ii> >adj;
bool v[100005] = {0};
ll val[100005] = {0};
vector<ll>ex[100005];
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]){
	adj.assign(n+5,vector<ii>());
	priority_queue<ii>ek;
	f(i,0,n){
		ex[i].pb(1e9);
		ex[i].pb(1e9);
		val[i] = 1e9;
		ek.push(ii(-val[i],i));
	}
	f(i,0,m){
		adj[r[i][0]].pb(ii(r[i][1],l[i]));
		adj[r[i][1]].pb(ii(r[i][0],l[i]));
	}
	f(i,0,k){
		ll z = p[i];
		v[z] = 1;
		val[z] = 0;
		for(auto x:adj[z]){
			if(!v[x.F]){
				ex[x.F].pb(val[z] + x.S);
				sort(ex[x.F].begin(),ex[x.F].end());
				ex[x.F].pop_back();
				val[x.F] = ex[x.F][1];
				ek.push(ii(-val[x.F],x.F));
			}	
		}
	}
	while(!ek.empty()){
		ii f = ek.top();
		ek.pop();
		if(v[f.S] || -f.F > val[f.S]){
			continue;
		}
		ll z = f.S;
		v[z] = 1;
		for(auto x:adj[z]){
			if(!v[x.F]){
				ex[x.F].pb(val[z] + x.S);
				sort(ex[x.F].begin(),ex[x.F].end());
				ex[x.F].pop_back();
				val[x.F] = ex[x.F][1];
				ek.push(ii(-val[x.F],x.F));
			}	
		}
	}
	return val[0];
}

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