Submission #756622

#	Time	Username	Problem	Language	Result	Execution time	Memory
756622		siewjh	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	482 ms	45240 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int inf = 1e9 + 7;
vector<pair<int, int>> adj[MAXN];
int dist[MAXN], dist1[MAXN], vis[MAXN];
bool isexit[MAXN];

int travel_plan(int nodes, int edges, int elist[][2], int elen[], int exits, int exarr[]){
	for (int i = 0; i < edges; i++){
		int a = elist[i][0], b = elist[i][1], d = elen[i];
		adj[a].push_back({b, d});
		adj[b].push_back({a, d});
	}
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	for (int i = 0; i < nodes; i++) dist[i] = dist1[i] = inf;
	for (int i = 0; i < exits; i++){
		dist[exarr[i]] = dist1[exarr[i]] = 0;
		pq.push({0, exarr[i]});
		vis[exarr[i]] = 1;
	}
	while (!pq.empty()){
		int d = pq.top().first, x = pq.top().second; pq.pop();
		if (d > dist1[x]) continue;
		if (vis[x] > 1) continue;
		if (vis[x] == 1){
			for (auto nxt : adj[x]){
				int nn = nxt.first, nd = nxt.second;
				if (d + nd < dist[nn]){
					dist1[nn] = dist[nn];
					dist[nn] = d + nd;
					pq.push({dist[nn], nn});
				}
				else if (d + nd < dist1[nn]){
					dist1[nn] = d + nd;
					pq.push({dist1[nn], nn});
				}
			}
		}
		vis[x]++;
	}
	return dist1[0];
}

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