oj.uz

Submission #604257

# Submission time Handle Problem Language Result Execution time Memory
604257 2022-07-25T02:07:16 Z penguinhacker Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 470 ms 61136 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

#define ar array

const int mxN=1e5;
int n, m, d[mxN][2];
vector<ar<int, 2>> adj[mxN];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	n=N, m=M;
	for (int i=0; i<m; ++i) {
		int u=R[i][0], v=R[i][1], w=L[i];
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	memset(d, 0x3f, sizeof(d));
	priority_queue<ar<int, 2>, vector<ar<int, 2>>, greater<ar<int, 2>>> pq;
	for (int i=0; i<K; ++i) {
		int u=P[i];
		d[u][0]=d[u][1]=0;
		pq.push({0, u});
	}
	while(pq.size()) {
		int cd=pq.top()[0], u=pq.top()[1];
		pq.pop();
		if (cd!=d[u][1])
			continue;
		for (auto [v, w] : adj[u]) {
			int last=d[v][1];
			if (cd+w<d[v][0])
				d[v][1]=d[v][0], d[v][0]=cd+w;
			else if (cd+w<d[v][1])
				d[v][1]=cd+w;
			if (d[v][1]<last)
				pq.push({d[v][1], v});
		}
	}
	return d[0][1];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 3 ms 3440 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 3 ms 3440 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 3 ms 3440 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 3 ms 3440 KB Output is correct
9 Correct 3 ms 3668 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 3 ms 3564 KB Output is correct
12 Correct 5 ms 3924 KB Output is correct
13 Correct 5 ms 4076 KB Output is correct
14 Correct 2 ms 3412 KB Output is correct
15 Correct 3 ms 3444 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 3 ms 3440 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 3 ms 3440 KB Output is correct
9 Correct 3 ms 3668 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 3 ms 3564 KB Output is correct
12 Correct 5 ms 3924 KB Output is correct
13 Correct 5 ms 4076 KB Output is correct
14 Correct 2 ms 3412 KB Output is correct
15 Correct 3 ms 3444 KB Output is correct
16 Correct 381 ms 57812 KB Output is correct
17 Correct 68 ms 13704 KB Output is correct
18 Correct 87 ms 15160 KB Output is correct
19 Correct 470 ms 61136 KB Output is correct
20 Correct 288 ms 50276 KB Output is correct
21 Correct 34 ms 8200 KB Output is correct
22 Correct 274 ms 46560 KB Output is correct