oj.uz

Submission #392918

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

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

	for (int 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<int> d1(n, INF), d2(n, INF);
	priority_queue<ar<int,2>, vector<ar<int,2>>, greater<ar<int,2>>> pq;
	for (int i = 0; i < k; i++) {
		d1[P[i]] = d2[P[i]] = 0;
		pq.push({0, P[i]});
	}

	while (!pq.empty()) {
		int 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 1 ms 204 KB Output is correct
2 Correct 1 ms 204 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 1 ms 204 KB Output is correct
2 Correct 1 ms 204 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 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -