Submission #462381

#	Time	Username	Problem	Language	Result	Execution time	Memory
462381		Khizri	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	540 ms	90092 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back		 
#define F first																 
#define S second 															 
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
#define endl "\n"
const int mxn=1e5+5;
ll isexit[mxn],color[mxn],n,m,arr[mxn],dis[mxn][2];
vector<pll>vt[mxn];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	n=N,m=M;
	for(int i=0;i<m;i++){
		vt[R[i][0]].pb({R[i][1],L[i]});
		vt[R[i][1]].pb({R[i][0],L[i]});
	}
	priority_queue<pll,vector<pll>,greater<pll>>q;
	for(int i=0;i<n;i++){
		dis[i][0]=dis[i][1]=INF;
	}
	for(int i=0;i<K;i++){
		q.push({0,P[i]});
		dis[P[i]][0]=dis[P[i]][1]=0;
	}
	while(q.size()){
		pll p=q.top();
		q.pop();
		ll u=p.S,sum=p.F;
		if(u==0){
			return sum;
		}
		if(color[u]){
			continue;
		}
		color[u]=1;
		for(pll xx:vt[u]){
			int v=xx.F,x=xx.S;
			if(dis[v][0]>dis[u][1]+x){
				dis[v][1]=dis[v][0];
				dis[v][0]=dis[u][1]+x;
				if(dis[v][1]!=INF){
					q.push({dis[v][1],v});
				}
			}
			else if(dis[v][1]>dis[u][1]+x){
				dis[v][1]=dis[u][1]+x;
				q.push({dis[v][1],v});
			}
		}
	}
	return 0;
}

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