oj.uz

Submission #783011

# Submission time Handle Problem Language Result Execution time Memory
783011 2023-07-14T14:11:17 Z zsombor Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 315 ms 63108 KB 
#include <iostream>
#include <vector>
#include <queue>
#include "crocodile.h"
using namespace std;

vector <vector <pair <int, int>>> g(1e5);
vector <int> o1(1e5, 2e9);
vector <int> o2(1e5, 2e9);
vector <bool> done(1e5, false);
priority_queue <pair <int, int>> pq;

bool update(int i, int val) {
	if (val < o1[i]) { o2[i] = o1[i]; o1[i] = val; return true; }
	if (val < o2[i]) { o2[i] = val; return true; }
	return false;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	int a, b, w;
	for (int i = 0; i < M; i++) {
		a = R[i][0]; b = R[i][1]; w = L[i];
		g[a].push_back({ b,w });
		g[b].push_back({ a,w });
	}
	for (int i = 0; i < K; i++) {
		o1[P[i]] = o2[P[i]] = 0;
		pq.push({ 0,P[i] });
	}
	while (!done[0]) {
		a = pq.top().second; pq.pop();
		if (done[a]) continue;
		done[a] = true;
		for (auto p : g[a]) {
			b = p.first; w = p.second;
			if (update(b, o2[a] + w)) pq.push({ -o2[b], b });
		}
	}
	return o2[0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3464 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3540 KB Output is correct
5 Correct 2 ms 3540 KB Output is correct
6 Correct 2 ms 3472 KB Output is correct
7 Correct 3 ms 3540 KB Output is correct
8 Correct 2 ms 3500 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3464 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3540 KB Output is correct
5 Correct 2 ms 3540 KB Output is correct
6 Correct 2 ms 3472 KB Output is correct
7 Correct 3 ms 3540 KB Output is correct
8 Correct 2 ms 3500 KB Output is correct
9 Correct 3 ms 3668 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 3 ms 3540 KB Output is correct
12 Correct 4 ms 3924 KB Output is correct
13 Correct 6 ms 4012 KB Output is correct
14 Correct 2 ms 3468 KB Output is correct
15 Correct 2 ms 3540 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3464 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3540 KB Output is correct
5 Correct 2 ms 3540 KB Output is correct
6 Correct 2 ms 3472 KB Output is correct
7 Correct 3 ms 3540 KB Output is correct
8 Correct 2 ms 3500 KB Output is correct
9 Correct 3 ms 3668 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 3 ms 3540 KB Output is correct
12 Correct 4 ms 3924 KB Output is correct
13 Correct 6 ms 4012 KB Output is correct
14 Correct 2 ms 3468 KB Output is correct
15 Correct 2 ms 3540 KB Output is correct
16 Correct 283 ms 58644 KB Output is correct
17 Correct 69 ms 14848 KB Output is correct
18 Correct 65 ms 15864 KB Output is correct
19 Correct 315 ms 63108 KB Output is correct
20 Correct 222 ms 50408 KB Output is correct
21 Correct 34 ms 8508 KB Output is correct
22 Correct 250 ms 46776 KB Output is correct