Submission #136911

#	Time	Username	Problem	Language	Result	Execution time	Memory
136911		eohomegrownapps	Crocodile's Underground City (IOI11_crocodile)	C++14	46 / 100	7 ms	4472 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

vector<vector<pair<int,int> > > adjlist;
int INF = 100000000;
vector<bool> isEnd;
vector<bool> visited;
vector<vector<int> > dp;
int dfs(int x, int pred){
	if (dp[x][pred]!=-1){
		return x;
	}
	//cout<<x<<endl;
	visited[x]=true;
	int min1 = INF;
	int min2 = INF;
	if (isEnd[x]){
		visited[x]=false;
		return dp[x][pred]=0;
	}
	for (auto p : adjlist[x]){
		if (visited[p.second]){
			continue;
		}
		int distance = p.first+dfs(p.second,x);
		if (distance<min1){
			min2=min1;
			min1=distance;
		} else if (distance<min2){
			min2=distance;
		}
	}
	visited[x]=false;
	return dp[x][pred]=min2;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	adjlist.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);
	dp.resize(N+1,vector<int>(N+1,-1));
	for (int i = 0; i<K; i++){
		isEnd[P[i]]=true;
	}
	return dfs(0,N);
}

• Subtask 1: 46 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11