oj.uz

Submission #335759

# Submission time Handle Problem Language Result Execution time Memory
335759 2020-12-13T22:08:47 Z nikatamliani Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 1112 ms 75336 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	priority_queue<pair<int,int>> q; 
	vector<vector<pair<int,int>>> edges(N);
	for(int i = 0; i < M; ++i) {
		edges[R[i][0]].push_back({R[i][1], L[i]});
		edges[R[i][1]].push_back({R[i][0], L[i]});
	}
	vector<bool> seen(N), vis(N);
	vector<int> dist(N);
	for(int i = 0; i < K; ++i) {
		q.push({0, P[i]});
		seen[P[i]] = 1;
	}
	while(!q.empty()) {
		pair<int,int> p = q.top(); q.pop();
		if(!seen[p.second]) {
			seen[p.second] = 1;
			continue;
		}
		if(vis[p.second]) continue;
		vis[p.second] = true;
		dist[p.second] = -p.first;
		for(pair<int,int> to : edges[p.second]) {
			q.push({-to.second+p.first, to.first});
		}
	}
	return dist[0];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 4 ms 748 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 3 ms 492 KB Output is correct
12 Correct 7 ms 1260 KB Output is correct
13 Correct 6 ms 1260 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 2 ms 492 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 4 ms 748 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 3 ms 492 KB Output is correct
12 Correct 7 ms 1260 KB Output is correct
13 Correct 6 ms 1260 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 2 ms 492 KB Output is correct
16 Correct 1030 ms 71204 KB Output is correct
17 Correct 96 ms 13420 KB Output is correct
18 Correct 132 ms 14828 KB Output is correct
19 Correct 1112 ms 75336 KB Output is correct
20 Correct 713 ms 64016 KB Output is correct
21 Correct 60 ms 5996 KB Output is correct
22 Correct 603 ms 44904 KB Output is correct