Submission #964532

#	Time	Username	Problem	Language	Result	Execution time	Memory
964532		UmairAhmadMirza	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	576 ms	63760 KiB

crocodile

#include <bits/stdc++.h>
using namespace std;
int const MN=1e5+5;
int const inf=1e9+5;
vector<pair<int,int>> adj[MN];
int maxa[MN],secmaxa[MN];
bool ex[MN];
set<pair<int,int>> d;
void dijikstra(){
	while(d.size()){
		auto p=d.begin();
		int dis=(*p).first;
		int node=(*p).second;
		// cerr<<node<<' '<<dis<<endl;
		d.erase(p);
		if(node==0)
			continue;
		for(auto i:adj[node]){
			int di=dis+i.second;
			if(di>=secmaxa[i.first])
				continue;
			d.erase({secmaxa[i.first],i.first});
			if(di<maxa[i.first]){
				secmaxa[i.first]=maxa[i.first];
				maxa[i.first]=di;
			}
			else
				secmaxa[i.first]=di;
			d.insert({secmaxa[i.first],i.first});
		}
	}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
	for (int i = 0; i < M; ++i)
	{
		int u=R[i][0];
		int v=R[i][1];
		adj[u].push_back({v,L[i]});
		adj[v].push_back({u,L[i]});
	}
	for (int i = 0; i < N; ++i)
		maxa[i]=inf,secmaxa[i]=inf;
	for (int i = 0; i < K; ++i)
	{
		maxa[P[i]]=0;
		secmaxa[P[i]]=0;
		d.insert({0,P[i]});
	}
	dijikstra();
	// cout<<"return"<<endl;
	return secmaxa[0];
}

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