oj.uz

Submission #1073828

# Submission time Handle Problem Language Result Execution time Memory
1073828 2024-08-24T22:52:34 Z ssitaram Crocodile's Underground City (IOI11_crocodile) C++17
89 / 100
 291 ms 76744 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
	vector<vector<pair<ll, ll>>> adj(n);
	for (ll i = 0; i < m; ++i) {
		adj[r[i][0]].push_back({r[i][1], l[i]});
		adj[r[i][1]].push_back({r[i][0], l[i]});
	}
	priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
	vector<priority_queue<ll>> best2(n);
	for (ll i = 0; i < k; ++i) {
		pq.push({0, p[i]});
		best2[p[i]].push(0);
		best2[p[i]].push(0);
	}
	while (!pq.empty()) {
		pair<ll, ll> state = pq.top();
		pq.pop();
		if (state.first > best2[state.second].top()) continue;
		if (!state.second) {
			return state.first;
		}
		for (pair<ll, ll>& edge : adj[state.second]) {
			if (best2[edge.first].size() < 2) {
				best2[edge.first].push(state.first + edge.second);
				if (best2[edge.first].size() == 2) pq.push({best2[edge.first].top(), edge.first});
			} else if (state.first + edge.second < best2[edge.first].top()) {
				best2[edge.first].pop();
				best2[edge.first].push(state.first + edge.second);
				pq.push({best2[edge.first].top(), edge.first});
			}
		}
	}
	return 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 4700 KB Output is correct
5 Correct 1 ms 4700 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 4700 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 4700 KB Output is correct
5 Correct 1 ms 4700 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 4700 KB Output is correct
9 Correct 3 ms 4696 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 3 ms 5052 KB Output is correct
13 Correct 3 ms 4956 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct

Subtask #3
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 4700 KB Output is correct
5 Correct 1 ms 4700 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 4700 KB Output is correct
9 Correct 3 ms 4696 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 3 ms 5052 KB Output is correct
13 Correct 3 ms 4956 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 254 ms 66504 KB Output is correct
17 Correct 51 ms 20820 KB Output is correct
18 Correct 63 ms 20820 KB Output is correct
19 Correct 291 ms 76744 KB Output is correct
20 Correct 178 ms 53336 KB Output is correct
21 Correct 26 ms 11100 KB Output is correct
22 Incorrect 204 ms 51388 KB Output isn't correct
23 Halted 0 ms 0 KB -