oj.uz

Submission #76876

# Submission time Handle Problem Language Result Execution time Memory
76876 2018-09-19T01:59:31 Z shoemakerjo Crocodile's Underground City (IOI11_crocodile) C++14
89 / 100
 718 ms 101096 KB 
#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;
#define pii pair<int, int>
#define maxn 100010
const int bil = 1000000000;
vector<vector<pii>> adj(maxn);
int 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]));
	}

	int 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 2860 KB Output is correct
3 Correct 4 ms 2920 KB Output is correct
4 Correct 5 ms 3140 KB Output is correct
5 Correct 5 ms 3140 KB Output is correct
6 Correct 4 ms 3140 KB Output is correct
7 Correct 5 ms 3152 KB Output is correct
8 Correct 4 ms 3184 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 2860 KB Output is correct
3 Correct 4 ms 2920 KB Output is correct
4 Correct 5 ms 3140 KB Output is correct
5 Correct 5 ms 3140 KB Output is correct
6 Correct 4 ms 3140 KB Output is correct
7 Correct 5 ms 3152 KB Output is correct
8 Correct 4 ms 3184 KB Output is correct
9 Correct 6 ms 3296 KB Output is correct
10 Correct 4 ms 3296 KB Output is correct
11 Correct 5 ms 3296 KB Output is correct
12 Correct 8 ms 3740 KB Output is correct
13 Correct 7 ms 3808 KB Output is correct
14 Correct 4 ms 3808 KB Output is correct
15 Correct 5 ms 3808 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 2860 KB Output is correct
3 Correct 4 ms 2920 KB Output is correct
4 Correct 5 ms 3140 KB Output is correct
5 Correct 5 ms 3140 KB Output is correct
6 Correct 4 ms 3140 KB Output is correct
7 Correct 5 ms 3152 KB Output is correct
8 Correct 4 ms 3184 KB Output is correct
9 Correct 6 ms 3296 KB Output is correct
10 Correct 4 ms 3296 KB Output is correct
11 Correct 5 ms 3296 KB Output is correct
12 Correct 8 ms 3740 KB Output is correct
13 Correct 7 ms 3808 KB Output is correct
14 Correct 4 ms 3808 KB Output is correct
15 Correct 5 ms 3808 KB Output is correct
16 Correct 607 ms 59152 KB Output is correct
17 Correct 126 ms 59152 KB Output is correct
18 Correct 158 ms 59152 KB Output is correct
19 Correct 718 ms 86876 KB Output is correct
20 Correct 341 ms 89700 KB Output is correct
21 Correct 58 ms 89700 KB Output is correct
22 Incorrect 412 ms 101096 KB Output isn't correct