Submission #153348

#	Time	Username	Problem	Language	Result	Execution time	Memory
153348		junodeveloper	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	809 ms	90136 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll INF=1e18;
int n,m;
ll D[100010],E[100010][2];
vector<pll> adj[100010];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	int i;
	for(i=0;i<M;i++) {
		int u=R[i][0],v=R[i][1];
		adj[u].push_back({v,L[i]});
		adj[v].push_back({u,L[i]});
	}
	priority_queue<pll,vector<pll>,greater<pll> > pq;
	for(i=0;i<N;i++) { 
		D[i]=INF;
		E[i][0]=E[i][1]=-1;
	}
	for(i=0;i<K;i++) {
		D[P[i]]=0;
		pq.push({D[P[i]],P[i]});
	}
	while(!pq.empty()) {
		ll w,u; tie(w,u)=pq.top(); pq.pop();
		if(D[u]<w) continue;
		for(auto& it:adj[u]) {
			ll v,c; tie(v,c)=it;
			ll d=w+c;
			if(E[v][0]==-1) E[v][0]=d;
			else if(d<E[v][0]) E[v][1]=E[v][0],E[v][0]=d;
			else if(E[v][1]==-1) E[v][1]=d;
			else if(d<E[v][1]) E[v][1]=d;
			if(E[v][1]!=-1) {
				if(E[v][1]<D[v]) {
					D[v]=E[v][1];
					pq.push({D[v],v});
				}
			}
		}
	}
	return D[0];
}

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