oj.uz

Submission #210553

# Submission time Handle Problem Language Result Execution time Memory
210553 2020-03-17T17:02:00 Z faremy Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 1247 ms 101564 KB 
#include "crocodile.h"

#include <vector>
#include <queue>


struct Edge
{
	Edge(int v, long long w) : dest(v), weight(w) {}
	int dest;
	long long weight;

	bool operator <(const Edge &other) const
	{
		return (other.weight < weight);
	}
};

const int MAXN = 1e5;
const long long INFTY = 1e18;

std::vector<Edge> graph[MAXN];
std::priority_queue<Edge> paths;
long long shortest[MAXN][2];


void dijkstra()
{
	while (!paths.empty())
	{
		int node = paths.top().dest;
		long long dist = paths.top().weight;
		paths.pop();

		if (shortest[node][0] == INFTY)
			shortest[node][0] = dist;
		else if (shortest[node][1] == INFTY)
		{
			shortest[node][1] = dist;
			for (Edge &edge : graph[node])
				paths.emplace(edge.dest, dist + edge.weight);
		}
	}
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	std::fill_n((long long *)shortest, N * 2, INFTY);
	for (int iEdge = 0; iEdge < M; iEdge++)
	{
		graph[R[iEdge][0]].emplace_back(R[iEdge][1], L[iEdge]);
		graph[R[iEdge][1]].emplace_back(R[iEdge][0], L[iEdge]);
	}

	for (int iExit = 0; iExit < K; iExit++)
	{
		shortest[P[iExit]][0] = 0;
		paths.emplace(P[iExit], 0);
	}

	dijkstra();
	return shortest[0][1];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 6 ms 2680 KB Output is correct
3 Correct 8 ms 2680 KB Output is correct
4 Correct 8 ms 2808 KB Output is correct
5 Correct 7 ms 2808 KB Output is correct
6 Correct 7 ms 2812 KB Output is correct
7 Correct 7 ms 2808 KB Output is correct
8 Correct 7 ms 2808 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 6 ms 2680 KB Output is correct
3 Correct 8 ms 2680 KB Output is correct
4 Correct 8 ms 2808 KB Output is correct
5 Correct 7 ms 2808 KB Output is correct
6 Correct 7 ms 2812 KB Output is correct
7 Correct 7 ms 2808 KB Output is correct
8 Correct 7 ms 2808 KB Output is correct
9 Correct 9 ms 3448 KB Output is correct
10 Correct 6 ms 2680 KB Output is correct
11 Correct 7 ms 2936 KB Output is correct
12 Correct 13 ms 3936 KB Output is correct
13 Correct 11 ms 4096 KB Output is correct
14 Correct 6 ms 2684 KB Output is correct
15 Correct 7 ms 2808 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 6 ms 2680 KB Output is correct
3 Correct 8 ms 2680 KB Output is correct
4 Correct 8 ms 2808 KB Output is correct
5 Correct 7 ms 2808 KB Output is correct
6 Correct 7 ms 2812 KB Output is correct
7 Correct 7 ms 2808 KB Output is correct
8 Correct 7 ms 2808 KB Output is correct
9 Correct 9 ms 3448 KB Output is correct
10 Correct 6 ms 2680 KB Output is correct
11 Correct 7 ms 2936 KB Output is correct
12 Correct 13 ms 3936 KB Output is correct
13 Correct 11 ms 4096 KB Output is correct
14 Correct 6 ms 2684 KB Output is correct
15 Correct 7 ms 2808 KB Output is correct
16 Correct 1127 ms 97216 KB Output is correct
17 Correct 111 ms 14456 KB Output is correct
18 Correct 150 ms 16632 KB Output is correct
19 Correct 1247 ms 101564 KB Output is correct
20 Correct 703 ms 87508 KB Output is correct
21 Correct 60 ms 8312 KB Output is correct
22 Correct 632 ms 51056 KB Output is correct