Submission #411587

#	Time	Username	Problem	Language	Result	Execution time	Memory
411587		albertolg101	Dreaming (IOI13_dreaming)	C++17	100 / 100	101 ms	20940 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"

using namespace std;

const int INF = 2e9;
using pii = pair<int, int>;

void Max (pair<pii, pii> &b, pii a)
{
	if(b.first < a)
	{
		b.second = b.first;
		b.first = a;
	}

	else if(b.second < a)
	{
		b.second = a;
	}
}

int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
	int n = N;
	vector<vector<pii>> g(n);

	for(int i = 0 ; i < M ; i++)
	{
		g[A[i]].push_back({B[i], T[i]});
		g[B[i]].push_back({A[i], T[i]});
	}

	vector<pair<pii, pii>> mm(n);

	vector<bool> flag(n);

	function<int(int, int)> dfs1 = [&](int nod, int father)
	{
		flag[nod] = true;

		for(auto i: g[nod])
		{
			if(i.first != father)
			{
				Max(mm[nod], {dfs1(i.first, nod) + i.second, i.first});
			}
		}

		return mm[nod].first.first ;
	};

	for(int i = 0 ; i < n ; i++)
	{
		if(!flag[i])
		{
			dfs1(i, -1);
		}
	}

	//for(auto i: mm)
	//	cout << i.first.first << ' ' << i.first.second << ' ' << i.second.first << ' ' << i.second.second << endl ;

	function<int(int, int, int)> dfs2 = [&](int nod, int father, int path)
	{
		flag[nod] = true;

		int ans = max(mm[nod].first.first, path); 

		for(auto i: g[nod])
		{
			if(i.first != father)
			{
				int tempPath = path;

				if(i.first == mm[nod].first.second)
					tempPath = max(tempPath, mm[nod].second.first);
				
				else
					tempPath = max(tempPath, mm[nod].first.first);

				ans = min(ans, dfs2(i.first, nod, tempPath + i.second));
			}
		}

		return ans;
	};

	flag = vector<bool> (n, false);
	vector<int> vans;

	for(int i = 0 ; i < n ; i++)
	{
		if(!flag[i])
			vans.push_back(dfs2(i, -1, 0));
	}

	//for(auto i: vans)
	//	cout << i << ' ' ; 
	//cout << endl ;

	int ans = 0;
	for(auto i: mm)
		ans = max(ans, i.first.first + i.second.first);

	if(vans.size() <= 1)
		return ans;

	else
	{
		sort(vans.rbegin(), vans.rend());
		ans = max(ans, vans[0] + vans[1] + L);
		if(vans.size() >= 3)
			ans = max(ans, vans[1] + vans[2] + 2 * L);

		return ans;
	}
}

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23