oj.uz

Submission #1073834

# Submission time Handle Problem Language Result Execution time Memory
1073834 2024-08-24T23:06:31 Z ssitaram Crocodile's Underground City (IOI11_crocodile) C++17
0 / 100
 7 ms 9308 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]) throw 1;
		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
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 Runtime error 7 ms 9308 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

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 Runtime error 7 ms 9308 KB Execution killed with signal 6
6 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 Runtime error 7 ms 9308 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -