oj.uz

Submission #137945

# Submission time Handle Problem Language Result Execution time Memory
137945 2019-07-28T15:11:33 Z eohomegrownapps Crocodile's Underground City (IOI11_crocodile) C++14
46 / 100
 2000 ms 504 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

vector<vector<pair<int,int> > > adjlist;
vector<vector<pair<int,int> > > treeadjlist;
int INF = 100000000;
vector<bool> isEnd;
vector<bool> visited;
vector<pair<int,int> > predecessor;
vector<int> distances;

int dfs(int x){
	//cout<<x<<endl;
	visited[x]=true;
	int min1 = INF;
	int min2 = INF;
	if (isEnd[x]){
		visited[x]=false;
		return 0;
	}
	for (auto p : treeadjlist[x]){
		if (visited[p.second]){
			continue;
		}
		int distance = p.first+dfs(p.second);
		if (distance<min1){
			min2=min1;
			min1=distance;
		} else if (distance<min2){
			min2=distance;
		}
	}
	visited[x]=false;
	return min2;
}

int origdfs(int x){
	//cout<<x<<endl;
	visited[x]=true;
	int min1 = INF;
	int min2 = INF;
	if (isEnd[x]){
		visited[x]=false;
		return 0;
	}
	for (auto p : adjlist[x]){
		if (visited[p.second]){
			continue;
		}
		int distance = p.first+origdfs(p.second);
		if (distance<min1){
			min2=min1;
			min1=distance;
		} else if (distance<min2){
			min2=distance;
		}
	}
	visited[x]=false;
	return min2;
}

void dijkstra(int start){
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
	pq.push(make_pair(start,0));
	distances[start]=0;
	while (pq.size()>0){
		auto f = pq.top();
		pq.pop();
		if (distances[f.second]<f.first){
			continue;
		}
		if (predecessor[f.second].first!=-1){
			treeadjlist[predecessor[f.second].second].push_back(make_pair(predecessor[f.second].first,f.second));
		}
		for (auto i : adjlist[f.second]){
			if (distances[i.second]>distances[f.second]+i.first){
				distances[i.second]=distances[f.second]+i.first;
				pq.push(make_pair(distances[i.second],i.second));
				predecessor[i.second]=make_pair(i.first,f.second);
			}
		}
	}
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	adjlist.resize(N);
	treeadjlist.resize(N);
	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]));
	}
	isEnd.resize(N,false);
	visited.resize(N,false);
	distances.resize(N,INF);
	predecessor.resize(N,make_pair(-1,-1));
	for (int i = 0; i<K; i++){
		isEnd[P[i]]=true;
	}
	dijkstra(0);
	int d = dfs(0);
	if (d!=INF){
		return d;
	} else {
		visited.resize(N,false);
		return origdfs(0);
	}
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 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 2 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
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 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 2 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 504 KB Output is correct
10 Execution timed out 2052 ms 376 KB Time limit exceeded
11 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 3 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 2 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 504 KB Output is correct
10 Execution timed out 2052 ms 376 KB Time limit exceeded
11 Halted 0 ms 0 KB -