Submission #116027

#	Time	Username	Problem	Language	Result	Execution time	Memory
116027		mosesmayer	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	798 ms	73196 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pll;

struct Edge{
	int v;LL w;
	Edge(){}
	Edge(int v, LL w): v(v), w(w) {}
	bool operator< (const Edge &rhs) const{
		return w > rhs.w;
	}
};
const int mxsz = 1e5 + 3;

int n, m, k;
vector<Edge> adj[mxsz];
LL d[mxsz];
pll best[mxsz];
priority_queue<Edge> pq;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	n = N, m = M, k = K;
	fill(best, best+n, make_pair(1e18, 1e18));
	for (int i = 0, u, v; i < m; i++){
		u = R[i][0], v = R[i][1];
		adj[u].emplace_back(v, L[i]);
		adj[v].emplace_back(u, L[i]);
	}
	for (int i = 0; i < k; i++) pq.emplace(P[i], 0);
	for (int i = 0; i < k; i++) best[P[i]] = make_pair(0,0);
	while (!pq.empty()){
		Edge e = pq.top(); pq.pop();
		int u = e.v;
		//cout << u << ' ' << e.w << " {" << best[u].fi << ", " << best[u].se << '}'<< '\n';
	//	if (e.w < best[u].se) best[u].se = e.w;
	//	if (best[u].fi > best[u].se) swap(best[u].fi, best[u].se);
		if (best[u].se < e.w) continue;
		int v; LL w;
		for (Edge nx : adj[u]){
			v = nx.v, w = nx.w; LL c = e.w + w;
			//if (best[u].se > c){ swap(best[u].se, c); }
			if (best[v].fi > c){
				if (best[v].se > best[v].fi){
					pq.emplace(v, best[v].fi);
				}
				swap(best[v].fi, best[v].se);
				best[v].fi = c;
			} else if (best[v].se > c){
				pq.emplace(v, (best[v].se = c) );
			}
		}
	}
	LL ret = best[0].se;
	return (ret >= 1e18 ? -1 : ret);
	return n;
}

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