oj.uz

Submission #140665

# Submission time Handle Problem Language Result Execution time Memory
140665 2019-08-04T10:41:14 Z eohomegrownapps Crocodile's Underground City (IOI11_crocodile) C++14
89 / 100
 833 ms 77116 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();
	assert(secshortest[0]!=INF);
	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 380 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 376 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 380 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 376 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 760 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 888 KB Output is correct
13 Correct 5 ms 1016 KB Output is correct
14 Correct 3 ms 504 KB Output is correct
15 Correct 4 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 380 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 376 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 760 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 888 KB Output is correct
13 Correct 5 ms 1016 KB Output is correct
14 Correct 3 ms 504 KB Output is correct
15 Correct 4 ms 504 KB Output is correct
16 Correct 681 ms 67228 KB Output is correct
17 Correct 139 ms 16660 KB Output is correct
18 Correct 172 ms 18928 KB Output is correct
19 Correct 833 ms 77116 KB Output is correct
20 Correct 403 ms 52728 KB Output is correct
21 Correct 63 ms 7388 KB Output is correct
22 Incorrect 424 ms 48888 KB Output isn't correct