Submission #392751

#	Time	Username	Problem	Language	Result	Execution time	Memory
392751		ritul_kr_singh	악어의 지하 도시 (IOI11_crocodile)	C++17	100 / 100	694 ms	77128 KiB

crocodile

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

const ll INF = 1e18;

struct twoSet{
	ll x = INF, y = INF; // x < y
	bool insert(ll v){
		if(v >= y) return false;
		y = v;
		if(x > y) swap(x, y);
		return true;
	}
	ll get(){ return y; }
};

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
	vector<twoSet> dist(N);
	vector<pair<int, ll>> g[N];

	for(int i=0; i<M; ++i){
		g[R[i][0]].emplace_back(R[i][1], L[i]);
		g[R[i][1]].emplace_back(R[i][0], L[i]);
	}

	priority_queue<pair<ll, int>> q;

	bool vis[N]; fill(vis, vis + N, false);

	for(int i=0; i<K; ++i){
		q.emplace(0, P[i]);
		dist[P[i]].insert(0);
		dist[P[i]].insert(0);
	}

	while(!q.empty()){
		ll u = q.top().second, d = -q.top().first; q.pop();
		if(vis[u]) continue;
		vis[u] = true;
		for(auto &e : g[u]){
			ll v = e.first, w = e.second;
			if(dist[v].insert(d + w)) q.emplace(-dist[v].get(), v);
		}
	}
	return dist[0].get();
}

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