oj.uz

Submission #1073497

# Submission time Handle Problem Language Result Execution time Memory
1073497 2024-08-24T15:25:36 Z ssitaram Crocodile's Underground City (IOI11_crocodile) C++17
46 / 100
 2 ms 4700 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<int, int>>> adj(n);
	for (int 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, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
	vector<priority_queue<ll>> best2(n);
	for (int i = 0; i < k; ++i) {
		pq.push({0, p[i]});
		best2[p[i]].push(0);
	}
	while (!pq.empty()) {
		pair<ll, int> state = pq.top();
		pq.pop();
		if (state.first > best2[state.second].top()) continue;
		if (!state.second) {
			if (state.first > 1e9) throw 1;
			return state.first;
		}
		for (pair<int, int>& 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 2 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 2 ms 4440 KB Output is correct

Subtask #2
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 2 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 2 ms 4440 KB Output is correct
9 Incorrect 2 ms 4700 KB Output isn't correct
10 Halted 0 ms 0 KB -

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 2 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 2 ms 4440 KB Output is correct
9 Incorrect 2 ms 4700 KB Output isn't correct
10 Halted 0 ms 0 KB -