Submission #919848

#	Time	Username	Problem	Language	Result	Execution time	Memory
919848		Lalic	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	440 ms	64968 KiB

crocodile

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

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5+10;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9+7;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int act[MAXN], dist[MAXN][2];
vector<pii> g[MAXN];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	for(int i=0;i<N;i++) dist[i][0]=dist[i][1]=INF;
	
	for(int i=0;i<M;i++){
		g[R[i][0]].pb({R[i][1], L[i]});
		g[R[i][1]].pb({R[i][0], L[i]});
	}
	
	priority_queue<pii, vector<pii>, greater<>> pq;
	for(int i=0;i<K;i++){
		act[P[i]]=1;
		pq.push({0, P[i]});
		dist[P[i]][0]=dist[P[i]][1]=0;
	}
	
	while(!pq.empty()){
		pii curr=pq.top();
		pq.pop();
		
		if(!act[curr.se]){
			act[curr.se]=1;
			continue;
		}
		else if(act[curr.se]==2) continue;
		act[curr.se]=2;
		
		for(auto u : g[curr.se]){
			if(dist[curr.se][1]+u.se<dist[u.fi][0]){
				dist[u.fi][1]=dist[u.fi][0];
				dist[u.fi][0]=dist[curr.se][1]+u.se;
				pq.push({dist[u.fi][0], u.fi});
			}
			else if(dist[curr.se][1]+u.se<dist[u.fi][1]){
				dist[u.fi][1]=dist[curr.se][1]+u.se;
				pq.push({dist[u.fi][1], u.fi});
			}
		}
	}
	
	return dist[0][1];
}

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