Submission #756611

#	Time	Username	Problem	Language	Result	Execution time	Memory
756611		jamezzz	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	487 ms	47624 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

#define sf scanf
#define pf printf
#define pb push_back
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define INF 1023456789
#define LINF 1023456789123456789
#define lb(x,v) lower_bound(all(x),v)-x.begin()
#define disc(x) sort(all(x)),x.resize(unique(all(x))-x.begin())
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll,int> li;

#define maxn 100005

ll d[maxn],d2[maxn];
vector<ii> AL[maxn];

int travel_plan(int N,int M,int R[][2],int L[],int K,int P[]){
	for(int i=0;i<M;++i){
		int a=R[i][0],b=R[i][1],w=L[i];
		AL[a].pb({b,w});
		AL[b].pb({a,w});
	}
	priority_queue<li,vector<li>,greater<li>> pq;
	fill(d,d+N,LINF);
	fill(d2,d2+N,LINF);
	for(int i=0;i<K;++i){
		d[P[i]]=d2[P[i]]=0;
		pq.push({0,P[i]});
	}
	while(!pq.empty()){
		auto[cd,u]=pq.top();pq.pop();
		if(cd!=d2[u])continue;
		for(auto[v,w]:AL[u]){
			ll nd=cd+w;
			if(nd<d[v]){
				if(d[v]<d2[v]){
					d2[v]=d[v];
					pq.push({d2[v],v});
				}
				d[v]=nd;
			}
			else if(nd<d2[v]){
				d2[v]=nd;
				pq.push({d2[v],v});
			}
		}
	}
	return d2[0];
}

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