oj.uz

Submission #1005148

# Submission time Handle Problem Language Result Execution time Memory
1005148 2024-06-22T08:02:34 Z coolboy19521 Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 1400 ms 211120 KB 
#include "bits/stdc++.h"
#include "crocodile.h"
#define i64 long long

using namespace std;

const i64 inf = 1e18 + 18;
const i64 sz = 1e5 + 5;

vector<vector<i64>> aj[sz];

bool vi[sz];
i64 d[sz][2];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	for (int i = 0; i < M; i ++) {
		i64 le = R[i][0];
		i64 ri = R[i][1];
		aj[le].push_back({ri, L[i]});
		aj[ri].push_back({le, L[i]});
	}

	for (i64 i = 0; i < N; i ++) {
		d[i][0] = inf;
		d[i][1] = inf;
	}

	priority_queue<vector<i64>> pq;

	for (i64 i = 0; i < K; i ++) {
		pq.push({0, P[i]});
		d[P[i]][0] = 0;
		d[P[i]][1] = 0;
	}

	while (!pq.empty()) {
		auto vc = pq.top();
		pq.pop();

		i64 v = vc[1];
		i64 ev = -vc[0];

		if (vi[v]) {
			continue;
		}

		vi[v] = true;

		if (ev >= inf) {
			continue;
		}

		for (auto& uc : aj[v]) {
			i64 u = uc[0];
			i64 eu = uc[1];

			if (vi[u]) {
				continue;
			}

			if (ev + eu < d[u][0]) {
				d[u][1] = d[u][0];
				d[u][0] = ev + eu;
			} else {
				d[u][1] = min(d[u][1], ev + eu);
			}

			pq.push({-d[u][1], u});
		}
	}

	return d[0][1];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 1 ms 6604 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 1 ms 6604 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 4 ms 7516 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 2 ms 7004 KB Output is correct
12 Correct 6 ms 8284 KB Output is correct
13 Correct 5 ms 8376 KB Output is correct
14 Correct 1 ms 6612 KB Output is correct
15 Correct 2 ms 6748 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 1 ms 6604 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 4 ms 7516 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 2 ms 7004 KB Output is correct
12 Correct 6 ms 8284 KB Output is correct
13 Correct 5 ms 8376 KB Output is correct
14 Correct 1 ms 6612 KB Output is correct
15 Correct 2 ms 6748 KB Output is correct
16 Correct 1219 ms 205508 KB Output is correct
17 Correct 92 ms 40960 KB Output is correct
18 Correct 139 ms 43656 KB Output is correct
19 Correct 1400 ms 211120 KB Output is correct
20 Correct 716 ms 174316 KB Output is correct
21 Correct 50 ms 23308 KB Output is correct
22 Correct 579 ms 144904 KB Output is correct