Submission #731770

#	Time	Username	Problem	Language	Result	Execution time	Memory
731770		beaboss	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	980 ms	117280 KiB

crocodile

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<ll, ll> pii;
typedef vector<ll> vi;

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
	vector<vector<pii> > adj(n);

	for (int i = 0; i < m; i++) {
		adj[r[i][0]].pb({r[i][1], l[i]});
		adj[r[i][1]].pb({r[i][0], l[i]});
	}

	vector<int> d1(n, -1);
	vector<int> d2(n, -1);

	priority_queue<pii> q;

	for (int i = 0; i < k; i++) {
		d1[p[i]] = 0;
		d2[p[i]] = 0;
		for (auto val: adj[p[i]]) q.push({-val.s, val.f});
	}

	while (!q.empty()) {
		int cur, dist;
		tie(dist, cur) = q.top();
		q.pop();

		if (d1[cur] == -1) {
			d1[cur] = -dist;
			continue;
		} else if (d2[cur] == -1) {
			d2[cur] = -dist; 
		} else {
			continue;
		}

		for (auto val: adj[cur]) {
			q.push({dist - val.s, val.f});
		}
	}



	return d2[0];
}

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