oj.uz

Submission #20729

# Submission time Handle Problem Language Result Execution time Memory
20729 2017-02-14T03:52:46 Z jjwdi0 Crocodile's Underground City (IOI11_crocodile) C++11
100 / 100
 769 ms 153172 KB 
#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> v[100003];
int D[100003][2];
bool visited[100003];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	for(int i=0; i<M; i++) {
		int x = R[i][0], y = R[i][1], z = L[i];
		x++, y++;
		v[x].push_back({y, z});
		v[y].push_back({x, z});
	}
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	for(int i=0; i<=N; i++) D[i][0] = D[i][1] = 1e9;
	for(int i=0; i<K; i++) D[P[i] + 1][0] = D[P[i] + 1][1] = 0, pq.push({0, P[i] + 1});
	while(!pq.empty()) {
		int cost = pq.top().first, u = pq.top().second; pq.pop();
		if(visited[u]) continue;
		visited[u] = 1;
		for(auto it : v[u]) {
			int c = cost + it.second, ne = it.first;
			if(visited[ne]) continue;
			if(D[ne][0] > c) {
				D[ne][1] = D[ne][0];
				D[ne][0] = c;
				if(D[ne][1] < 1e9) pq.push({D[ne][1], ne});
			}
			else if(D[ne][1] > c) {
				D[ne][1] = c;
				pq.push({c, ne});
			}
		}
	}
	return D[1][1];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 122624 KB Output is correct
2 Correct 0 ms 122624 KB Output is correct
3 Correct 0 ms 122624 KB Output is correct
4 Correct 0 ms 122756 KB Output is correct
5 Correct 0 ms 122760 KB Output is correct
6 Correct 0 ms 122624 KB Output is correct
7 Correct 0 ms 122756 KB Output is correct
8 Correct 0 ms 122624 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 122756 KB Output is correct
2 Correct 0 ms 122624 KB Output is correct
3 Correct 3 ms 122756 KB Output is correct
4 Correct 3 ms 122888 KB Output is correct
5 Correct 3 ms 122888 KB Output is correct
6 Correct 0 ms 122624 KB Output is correct
7 Correct 0 ms 122756 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 619 ms 149276 KB Output is correct
2 Correct 93 ms 127376 KB Output is correct
3 Correct 126 ms 128564 KB Output is correct
4 Correct 769 ms 153172 KB Output is correct
5 Correct 316 ms 145512 KB Output is correct
6 Correct 43 ms 125000 KB Output is correct
7 Correct 383 ms 140972 KB Output is correct