oj.uz

Submission #392924

# Submission time Handle Problem Language Result Execution time Memory
392924 2021-04-22T10:01:30 Z Aryan_Raina Crocodile's Underground City (IOI11_crocodile) C++14
0 / 100
 4 ms 332 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

#define ar array
#define ll long long
const ll INF = 1e15;
int travel_plan(int n, int m, int R[][2], int L[], int k, int P[]) {
	vector<ar<ll,2>> g[n];

	for (ll i = 0; i < m; i++) {
		g[R[i][0]].push_back({L[i], R[i][1]});
		g[R[i][1]].push_back({L[i], R[i][0]});
	}

	vector<ll> d1(n, INF), d2(n, INF);
	priority_queue<ar<ll,2>, vector<ar<ll,2>>, greater<ar<ll,2>>> pq;
	for (ll i = 0; i < k; i++) pq.push({d1[P[i]] = d2[P[i]] = 0, P[i]});

	while (!pq.empty()) {
		ll u = pq.top()[1], dist = pq.top()[0]; pq.pop();
		for (auto v : g[u]) {
			if (dist + v[0] < d1[v[1]]) d2[v[1]] = d1[v[1]], d1[v[1]] = dist + v[0];
			else if (dist + v[0] < d2[v[1]]) d2[v[1]] = dist + v[0];
			else continue;
			if (d2[v[1]] <= INF/2) pq.push({d2[v[1]], v[1]});
		}
	}
	return d2[0];
}

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 204 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 204 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 204 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -