oj.uz

Submission #1073835

# Submission time Handle Problem Language Result Execution time Memory
1073835 2024-08-24T23:06:50 Z ssitaram Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 286 ms 76312 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);
	}
	vector<bool> vis(n);
	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;
		}
		if (vis[state.second]) continue;
		vis[state.second] = 1;
		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 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4540 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 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 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4540 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 4696 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 3 ms 4956 KB Output is correct
13 Correct 3 ms 5052 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct

Subtask #3
11.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 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4540 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 4696 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 3 ms 4956 KB Output is correct
13 Correct 3 ms 5052 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 286 ms 66504 KB Output is correct
17 Correct 51 ms 20796 KB Output is correct
18 Correct 63 ms 20780 KB Output is correct
19 Correct 284 ms 76312 KB Output is correct
20 Correct 164 ms 53328 KB Output is correct
21 Correct 26 ms 11088 KB Output is correct
22 Correct 187 ms 51280 KB Output is correct