oj.uz

Submission #140662

# Submission time Handle Problem Language Result Execution time Memory
140662 2019-08-04T10:35:00 Z eohomegrownapps Crocodile's Underground City (IOI11_crocodile) C++14
89 / 100
 828 ms 77092 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll INF = 1e18;
vector<vector<pair<ll,ll> > > adjlist;
vector<ll> safe;
vector<ll> shortest;
vector<ll> secshortest;
ll n;

void dijkstra(){
	priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > pq;
	for (ll i : safe){
		pq.push(make_pair(0,i));
	}
	while (pq.size()>0){
		auto f = pq.top();
		pq.pop();
		if (f.first>secshortest[f.second]){
			continue;
		}
		//cout<<"process "<<f.second<<endl;
		for (auto i : adjlist[f.second]){
			if (secshortest[i.second]>secshortest[f.second]+i.first){
				if (secshortest[f.second]+i.first<=shortest[i.second]){
					secshortest[i.second]=shortest[i.second];
					shortest[i.second]=secshortest[f.second]+i.first;
				} else {
					secshortest[i.second]=secshortest[f.second]+i.first;
				}
				pq.push(make_pair(secshortest[i.second],i.second));
			}
		}
		/*for (ll i : shortest){
			cout<<(i==INF?-1:i)<<" ";
		}cout<<endl;
		for (ll i : secshortest){
			cout<<(i==INF?-1:i)<<" ";
		}cout<<endl;
		cout<<"==="<<endl;*/
	}
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	n=N;
	adjlist.resize(n);
	safe.resize(K);
	shortest.resize(n,INF);
	secshortest.resize(n,INF);
	for (int i = 0; i<M; i++){
		adjlist[R[i][0]].push_back(make_pair(L[i],R[i][1]));
		adjlist[R[i][1]].push_back(make_pair(L[i],R[i][0]));
	}
	for (int i = 0; i<K; i++){
		safe[i]=P[i];
		shortest[P[i]]=0;
		secshortest[P[i]]=0;
	}
	dijkstra();
	return secshortest[0];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 4 ms 632 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 6 ms 892 KB Output is correct
13 Correct 5 ms 1016 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 3 ms 504 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 4 ms 632 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 6 ms 892 KB Output is correct
13 Correct 5 ms 1016 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 3 ms 504 KB Output is correct
16 Correct 669 ms 67256 KB Output is correct
17 Correct 126 ms 16620 KB Output is correct
18 Correct 164 ms 18928 KB Output is correct
19 Correct 828 ms 77092 KB Output is correct
20 Correct 376 ms 52588 KB Output is correct
21 Correct 57 ms 7416 KB Output is correct
22 Incorrect 411 ms 48884 KB Output isn't correct