oj.uz

Submission #140666

# Submission time Handle Problem Language Result Execution time Memory
140666 2019-08-04T10:44:51 Z eohomegrownapps Crocodile's Underground City (IOI11_crocodile) C++14
0 / 100
 3 ms 504 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
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 Incorrect 3 ms 504 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
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 Incorrect 3 ms 504 KB Output isn't correct
6 Halted 0 ms 0 KB -

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 Incorrect 3 ms 504 KB Output isn't correct
6 Halted 0 ms 0 KB -