Submission #76622

#	Time	Username	Problem	Language	Result	Execution time	Memory
76622		teomrn	Dreaming (IOI13_dreaming)	C++14	100 / 100	111 ms	8852 KiB

dreaming

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

namespace Solve {
	vector <pair <int, int>> adia[100010];
	int g[100010];
	bool viz[100010];
	vector <int> dist;
	int tata[100010];
	int g_tata[100010];
	int n, ans = 0;

	int get_mij_diam(int nod) {

		auto calc_d = [](int nod) {
			tata[nod] = 0;
			vector <pair <int, pair <int, int>>> v = { { 0, { nod, 0 } } };
			pair <int, int> dmax = { 0, 0 };
			while (!v.empty()) {
				auto x = v.back();
				v.pop_back();
				viz[x.second.first] = 1;
				dmax = max(dmax, { x.first, x.second.first });
				for (auto i : adia[x.second.first]) {
					if (i.first != x.second.second) {
						tata[i.first] = x.second.first;
						g_tata[i.first] = i.second;
						v.push_back({ x.first + i.second, { i.first, x.second.first } });
					}
				}
			}
			return dmax;
		};
		nod = calc_d(nod).second;
		auto d = calc_d(nod);
		int best = 1e9;
		ans = max(ans, d.first);

		for (int i = d.second, l = d.first; i; l -= g_tata[i], i = tata[i])
			best = min(best, max(l, d.first - l));

		return best;
	}

	int solve(int l) {
		for (int i = 1; i <= n; i++)
			if (!viz[i])
				dist.push_back(get_mij_diam(i));
		sort(dist.rbegin(), dist.rend());
		if (dist.size() == 1)
			return ans;
		if (dist.size() == 2)
			return max(ans, l + dist[0] + dist[1]);
		return max(ans, max(2 * l + dist[1] + dist[2], l + dist[0] + dist[1]));
	}
}

int travelTime(int N, int M, int L,	int A[], int B[], int T[]) {
	Solve::n = N;
	for (int i = 0; i < M; i++)
		Solve::adia[A[i] + 1].push_back({ B[i] + 1, T[i] }), Solve::adia[B[i] + 1].push_back({ A[i] + 1, T[i] });
	return Solve::solve(L);
}
/*
int A[] = { 0, 8, 2, 5, 5, 1, 1, 10 };
int B[] = { 8, 2, 7, 11, 1, 3, 9, 6 };
int T[] = { 4, 2, 4, 3, 7, 1, 5, 3 };

int main()
{

	cout << travelTime(12, 8, 2, A, B, T);

	return 0;
}
*/

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