oj.uz

Submission #263342

# Submission time Handle Problem Language Result Execution time Memory
263342 2020-08-13T15:50:26 Z Berted Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 697 ms 61680 KB 
#include "crocodile.h"
#include <queue>
#include <vector>
#define vi vector<int>
#define pii pair<int, int>
#define fst first
#define snd second
#define vpi vector<pii>

using namespace std;

const int INF = 2e9;

priority_queue<pii, vector<pii>, greater<pii>> pq;
int dst[100001], mn[100001][2];
vpi adj[100001];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	for (int i = 0; i < N; i++)
	{
		dst[i] = mn[i][0] = mn[i][1] = INF;
	}
	for (int i = 0; i < M; i++)
	{
		int u = R[i][0], v = R[i][1];
		adj[u].emplace_back(v, L[i]);
		adj[v].emplace_back(u, L[i]);
	}
	for (int i = 0; i < K; i++)
	{
		dst[P[i]] = mn[P[i]][0] = mn[P[i]][1] = 0;
		pq.emplace(0, P[i]);
	}
	while (pq.size())
	{
		int u = pq.top().snd; int d = pq.top().fst; pq.pop();
		if (d == dst[u])
		{
			if (u == 0) break;
			for (auto v : adj[u])
			{
				if (d + v.snd < mn[v.fst][0])
				{
					mn[v.fst][1] = mn[v.fst][0];
					mn[v.fst][0] = d + v.snd;
				}
				else if (d + v.snd < mn[v.fst][1])
				{
					mn[v.fst][1] = d + v.snd;
				}
				if (mn[v.fst][1] < dst[v.fst]) 
				{
					dst[v.fst] = mn[v.fst][1];
					pq.push({mn[v.fst][1], v.fst});
				}
			}
		}
	}
	return dst[0];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 3 ms 2816 KB Output is correct
5 Correct 3 ms 2816 KB Output is correct
6 Correct 3 ms 2688 KB Output is correct
7 Correct 3 ms 2816 KB Output is correct
8 Correct 3 ms 2816 KB Output is correct
9 Correct 4 ms 2944 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 3 ms 2816 KB Output is correct
12 Correct 6 ms 3200 KB Output is correct
13 Correct 6 ms 3200 KB Output is correct
14 Correct 2 ms 2688 KB Output is correct
15 Correct 3 ms 2816 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 3 ms 2816 KB Output is correct
5 Correct 3 ms 2816 KB Output is correct
6 Correct 3 ms 2688 KB Output is correct
7 Correct 3 ms 2816 KB Output is correct
8 Correct 3 ms 2816 KB Output is correct
9 Correct 4 ms 2944 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 3 ms 2816 KB Output is correct
12 Correct 6 ms 3200 KB Output is correct
13 Correct 6 ms 3200 KB Output is correct
14 Correct 2 ms 2688 KB Output is correct
15 Correct 3 ms 2816 KB Output is correct
16 Correct 607 ms 57328 KB Output is correct
17 Correct 96 ms 14304 KB Output is correct
18 Correct 108 ms 15608 KB Output is correct
19 Correct 697 ms 61680 KB Output is correct
20 Correct 369 ms 49656 KB Output is correct
21 Correct 46 ms 7928 KB Output is correct
22 Correct 382 ms 46136 KB Output is correct