oj.uz

Submission #108300

# Submission time Handle Problem Language Result Execution time Memory
108300 2019-04-28T13:19:57 Z SecretAgent007 Crocodile's Underground City (IOI11_crocodile) C++17
89 / 100
 1153 ms 94460 KB 
#include <bits/stdc++.h>
using namespace std;

//#define int long long 

const long long INF = 1e18;

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]){
	
	vector< vector< pair<long long, long long> > > Graph(n);
	
	for(int i = 0; i < m; i++){
		Graph[r[i][0]].push_back(make_pair(l[i], r[i][1]));
		Graph[r[i][1]].push_back(make_pair(l[i], r[i][0]));
	}
	
	priority_queue< pair<long long, long long>, vector< pair<long long, long long> >, greater< pair<long long, long long> > > pq;
	
	vector< vector< long long > > dist(n, vector<long long>(2, INF));
	
	for(int i = 0; i < k; i++){
		dist[p[i]][0] = dist[p[i]][1] = 0;
		pq.push(make_pair(0,p[i]));
	}
	
	while(!pq.empty()){
		pair<int, int> pa = pq.top();
		pq.pop();
		
		int cost = pa.first;
		int node = pa.second;
		
		if(dist[node][1] != cost) continue;
		
		for(auto a : Graph[node]){
		
			if(dist[a.second][0] > a.first + cost){
				dist[a.second][1] = dist[a.second][0];
				dist[a.second][0] = a.first+cost;
				pq.push(make_pair(dist[a.second][1], a.second)); 
			}else if(dist[a.second][1] > a.first+cost){
				dist[a.second][1] = a.first+cost;
				pq.push(make_pair(dist[a.second][1], a.second));
			}
		
		}
		
	}
	
	return dist[0][1];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 4 ms 544 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 4 ms 544 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 3 ms 356 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 7 ms 1024 KB Output is correct
13 Correct 5 ms 1152 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 5 ms 512 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 4 ms 544 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 3 ms 356 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 7 ms 1024 KB Output is correct
13 Correct 5 ms 1152 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 5 ms 512 KB Output is correct
16 Correct 933 ms 83732 KB Output is correct
17 Correct 193 ms 23792 KB Output is correct
18 Correct 222 ms 25424 KB Output is correct
19 Correct 1153 ms 94460 KB Output is correct
20 Correct 418 ms 65844 KB Output is correct
21 Correct 59 ms 9976 KB Output is correct
22 Incorrect 466 ms 64372 KB Output isn't correct