Submission #927948

#	Time	Username	Problem	Language	Result	Execution time	Memory
927948		TAhmed33	Crocodile's Underground City (IOI11_crocodile)	C++98	100 / 100	566 ms	83372 KiB

crocodile

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 1e5;
ll inf = 1e12;
vector <pair <int, int>> adj[MAX + 5];
bool endd[MAX + 5];
int travel_plan (int n, int m, int r[][2], int w[], int k, int e[]) {
	for (int i = 1; i <= n; i++) {
		adj[i].clear();
		endd[i] = 0;
	}
	for (int i = 0; i < m; i++) {
		adj[r[i][0] + 1].push_back({r[i][1] + 1, w[i]});
		adj[r[i][1] + 1].push_back({r[i][0] + 1, w[i]});
	}
	ll dist[n + 1][2];
	for (int i = 1; i <= n; i++) dist[i][0] = dist[i][1] = inf;
	priority_queue <vector <ll>, vector <vector <ll>>, greater <vector <ll>>> pq;
	for (int i = 0; i < k; i++) {
		e[i]++;
		dist[e[i]][0] = dist[e[i]][1] = 0;
		pq.push({0, 0, e[i]});
	}
	while (!pq.empty()) {
		auto l = pq.top();
		pq.pop();
		if (dist[l[2]][0] < l[0]) continue;
		if (dist[l[2]][1] < l[1]) continue;
		for (auto j : adj[l[2]]) {
			bool flag = 1;
			if (j.second + l[0] < dist[j.first][1]) {
				dist[j.first][0] = dist[j.first][1];
				flag = 0;
				dist[j.first][1] = j.second + l[0];
			} else if (j.second + l[0] < dist[j.first][0]) {
				flag = 0;
				dist[j.first][0] = j.second + l[0];
			}
			if (!flag) pq.push({dist[j.first][0], dist[j.first][1], j.first});
		}
	}
	return dist[1][0];
}

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