oj.uz

Submission #76877

# Submission time Handle Problem Language Result Execution time Memory
76877 2018-09-19T02:01:16 Z shoemakerjo Crocodile's Underground City (IOI11_crocodile) C++14
89 / 100
 863 ms 77288 KB 
#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<ll, int>
#define maxn 100010
const ll bil = 2000000000LL;
vector<vector<pii>> adj(maxn);
ll dist[maxn][2];
priority_queue<pii, vector<pii>, greater<pii>> pq;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	for (int i = 0; i < N; i++) {
		dist[i][0] = dist[i][1] = bil;
	}
	int v;
	for (int i = 0; i < K; i++) {
		v = P[i];
		dist[v][0] = dist[v][1] = 0;
		pq.push(pii(0, v));
	}

	for (int i = 0; i < M; i++) {
		adj[R[i][0]].push_back(pii(R[i][1], L[i]));
		adj[R[i][1]].push_back(pii(R[i][0], L[i]));
	}

	ll d;
	while (!pq.empty()) {
		d = pq.top().first;
		v = pq.top().second;
		// cout << v << " : " << d << endl;
		pq.pop();
		if (dist[v][1] < d) continue;

		for (pii vv : adj[v]) {
			if (d + vv.second < dist[vv.first][0]) {
				dist[vv.first][1] = dist[vv.first][0];
				dist[vv.first][0] = d + vv.second;
				pq.push(pii(dist[vv.first][1], vv.first));
			}
			else if (d + vv.second < dist[vv.first][1]) {
				dist[vv.first][1] = d + vv.second;
				pq.push(pii(dist[vv.first][1], vv.first));
			}
		}

	}


	return dist[0][1];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2832 KB Output is correct
3 Correct 4 ms 2832 KB Output is correct
4 Correct 5 ms 2848 KB Output is correct
5 Correct 6 ms 2988 KB Output is correct
6 Correct 4 ms 2988 KB Output is correct
7 Correct 5 ms 2988 KB Output is correct
8 Correct 5 ms 3008 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2832 KB Output is correct
3 Correct 4 ms 2832 KB Output is correct
4 Correct 5 ms 2848 KB Output is correct
5 Correct 6 ms 2988 KB Output is correct
6 Correct 4 ms 2988 KB Output is correct
7 Correct 5 ms 2988 KB Output is correct
8 Correct 5 ms 3008 KB Output is correct
9 Correct 6 ms 3264 KB Output is correct
10 Correct 4 ms 3264 KB Output is correct
11 Correct 5 ms 3264 KB Output is correct
12 Correct 8 ms 3560 KB Output is correct
13 Correct 8 ms 3708 KB Output is correct
14 Correct 4 ms 3708 KB Output is correct
15 Correct 5 ms 3708 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2832 KB Output is correct
3 Correct 4 ms 2832 KB Output is correct
4 Correct 5 ms 2848 KB Output is correct
5 Correct 6 ms 2988 KB Output is correct
6 Correct 4 ms 2988 KB Output is correct
7 Correct 5 ms 2988 KB Output is correct
8 Correct 5 ms 3008 KB Output is correct
9 Correct 6 ms 3264 KB Output is correct
10 Correct 4 ms 3264 KB Output is correct
11 Correct 5 ms 3264 KB Output is correct
12 Correct 8 ms 3560 KB Output is correct
13 Correct 8 ms 3708 KB Output is correct
14 Correct 4 ms 3708 KB Output is correct
15 Correct 5 ms 3708 KB Output is correct
16 Correct 719 ms 68868 KB Output is correct
17 Correct 133 ms 68868 KB Output is correct
18 Correct 165 ms 68868 KB Output is correct
19 Correct 863 ms 77288 KB Output is correct
20 Correct 414 ms 77288 KB Output is correct
21 Correct 60 ms 77288 KB Output is correct
22 Incorrect 425 ms 77288 KB Output isn't correct