Submission #123611

#	Time	Username	Problem	Language	Result	Execution time	Memory
123611		johutha	Crocodile's Underground City (IOI11_crocodile)	C++14	46 / 100	4 ms	504 KiB

crocodile

#include "crocodile.h"
#include <vector>
#include <iostream>

using namespace std;

vector<int> vals;

vector<vector<pair<int,int>>> adjlist;

int dfs(int curr, int prev)
{
	if (vals[curr] != -1) return vals[curr];
	vals[curr] = 1e9;
	int fr = 1e9;
	int sec = 1e9;

	for (auto p : adjlist[curr])
	{
		int next = p.first;
		if (next == prev) continue;
		int val = dfs(next, curr) + p.second;
		if (val <= fr)
		{
			sec = fr;
			fr = val;
		}
		else if (val <= sec)
		{
			sec = val;
		}
	}
	//cout << curr << ": " << vals[curr] << "\n" << flush;
	return vals[curr] = sec;
}

int travel_plan(int n, int m, int R[][2], int L[], int k, int P[])
{
	vals.resize(n, -1);
	for (int i = 0; i < k; i++)
	{
		vals[P[i]] = 0;
	}
	adjlist.resize(n);
	for (int i = 0; i < m; i++)
	{
		adjlist[R[i][0]].push_back({R[i][1], L[i]});
		adjlist[R[i][1]].push_back({R[i][0], L[i]});
	}
	return dfs(0, -1);
}

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