oj.uz

Submission #1005149

# Submission time Handle Problem Language Result Execution time Memory
1005149 2024-06-22T08:02:50 Z vjudge1 Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 1371 ms 195088 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 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6744 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 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 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6744 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6748 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 3 ms 7260 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 5 ms 8024 KB Output is correct
13 Correct 6 ms 8284 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6744 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6744 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6748 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 3 ms 7260 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 5 ms 8024 KB Output is correct
13 Correct 6 ms 8284 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6744 KB Output is correct
16 Correct 1242 ms 188908 KB Output is correct
17 Correct 91 ms 37604 KB Output is correct
18 Correct 132 ms 40244 KB Output is correct
19 Correct 1371 ms 195088 KB Output is correct
20 Correct 710 ms 161520 KB Output is correct
21 Correct 44 ms 22032 KB Output is correct
22 Correct 542 ms 130568 KB Output is correct