Submission #388613

#	Time	Username	Problem	Language	Result	Execution time	Memory
388613		Vlatko	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	705 ms	77352 KiB

crocodile

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

using ll = long long;
using pli = pair<ll, int>;

const ll inf = 1e18;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {

	vector<pli> adj[N];

	for (int i = 0; i < M; ++i) {
		adj[R[i][0]].emplace_back(L[i], R[i][1]);
		adj[R[i][1]].emplace_back(L[i], R[i][0]);
//		cout << "edge " << R[i][0] << " - " << R[i][1] << " with weight " << L[i] << "\n";
	}

	priority_queue<pli, vector<pli>, greater<pli>> pq;
	bool vis[N];
	ll d1[N], d2[N];

	for (int i = 0; i < N; ++i) {
		vis[i] = false;
		d1[i] = d2[i] = inf;
	}

	for (int i = 0; i < K; ++i) {
		int s = P[i];
//		cout<<"source "<<s<<"\n";
		d1[s] = d2[s] = 0;
		pq.emplace(0, s);
	}

	while (!pq.empty()) {
		int u = pq.top().second;
		pq.pop();
		if (vis[u]) continue;
		vis[u] = true;
//		cout<<"u="<<u<<" d1="<<d1[u]<<" d2="<<d2[u]<<"\n";
		for (pli to : adj[u]) {
			int v = to.second;
			ll alt = d2[u] + to.first;
//			cout<<"  v="<<v<<" w="<<to.first<<" alt="<<alt<<"\n";
			if (d1[v] == d2[v]) {
				if (alt < d1[v]) {
					d1[v] = alt;
					pq.emplace(d2[v], v); // might be inf, but that's fine
//					cout<<"  first case\n";
				}
			} else {
				// d1[v] < d2[v]
				if (alt <= d1[v]) {
					d2[v] = d1[v];
					d1[v] = alt;
					pq.emplace(d2[v], v);
//					cout<<"  second case\n";
				} else if (alt < d2[v]) {
					d2[v] = alt;
					pq.emplace(d2[v], v);
//					cout<<"  third case\n";
				}
			}
		}
	}

	return d2[0];
}

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