oj.uz

Submission #1039501

# Submission time Handle Problem Language Result Execution time Memory
1039501 2024-07-31T01:26:06 Z sssamui Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 277 ms 61736 KB 
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	vector<int> min1(N, 1e9 + 1), min2(N, 1e9 + 1);
	vector<vector<pair<int, int>>> adj(N, vector<pair<int, int>>(0));
	for (int i = 0; i < M; i++)
	{
		adj[R[i][0]].push_back({ L[i], R[i][1] }), adj[R[i][1]].push_back({ L[i], R[i][0] });
	}

	priority_queue<pair<int, int>> djk;
	vector<bool> prc(N, false);
	for (int i = 0; i < K; i++)
	{
		min1[P[i]] = 0, min2[P[i]] = 0;
		djk.push({ 0, P[i]});
	}

	while (!djk.empty())
	{
		int d = -djk.top().first, node = djk.top().second;
		djk.pop();
		if ((d == min2[node]) && !prc[node])
		{
			prc[node] = true;
			for (pair<int, int> nxt : adj[node])
			{
				if (d + nxt.first < min1[nxt.second])
				{
					min2[nxt.second] = min1[nxt.second];
					min1[nxt.second] = d + nxt.first;
					djk.push({ -d - nxt.first, nxt.second });
				}

				else if (d + nxt.first < min2[nxt.second])
				{
					min2[nxt.second] = d + nxt.first;
					djk.push({ -d - nxt.first, nxt.second });
				}
			}
		}
	}

	return min2[0];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4552 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4440 KB Output is correct
12 Correct 3 ms 4696 KB Output is correct
13 Correct 2 ms 4900 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4552 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4440 KB Output is correct
12 Correct 3 ms 4696 KB Output is correct
13 Correct 2 ms 4900 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Correct 233 ms 57500 KB Output is correct
17 Correct 62 ms 15440 KB Output is correct
18 Correct 58 ms 16980 KB Output is correct
19 Correct 277 ms 61736 KB Output is correct
20 Correct 167 ms 47808 KB Output is correct
21 Correct 24 ms 9052 KB Output is correct
22 Correct 176 ms 46132 KB Output is correct