Submission #1143846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143846		buzdi	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	580 ms	77308 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int NMAX = 1e5;
const ll INF = 1e18;

struct PQElement {
	int node;
	ll d;
	bool operator < (const PQElement &other) const {
		return other.d < d;
	}
};

vector<pair<int, int>> g[NMAX + 1];
int n, m;
vector<ll> d[NMAX + 1];
char is_end[NMAX + 1];

void Dijkstra() {
	priority_queue<PQElement> pq;
	for(int i = 1; i <= n; i++) {
		if(is_end[i]) {
			pq.push({i, 0});
			pq.push({i, 0});
		}
	}

	while(!pq.empty()) {
		auto [node, curent_d] = pq.top();
		pq.pop();

		if(d[node].size() < 2) {
			d[node].push_back(curent_d);
			if(d[node].size() == 2) {
				for(auto [next_node, edge_d] : g[node]) {
					pq.push({next_node, curent_d + edge_d});
				}
			}
		}
	}
}

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++) {
		int a = R[i][0]; a++;
		int b = R[i][1]; b++;
		int c = L[i];

		g[a].emplace_back(b, c);
		g[b].emplace_back(a, c);
	}

	for(int i = 0; i < K; i++) {
		P[i]++;
		is_end[P[i]] = 1;
	}

	Dijkstra();
	return d[1][1];
}

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