Submission #776430

#	Time	Username	Problem	Language	Result	Execution time	Memory
776430		eliasol	Islands (IOI08_islands)	C++17	80 / 100	1179 ms	131072 KiB

islands

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <array>
#include <functional>

int main()
{
	int N;
	std::cin >> N;
	std::vector<std::vector<std::array<int, 3>>> graph(N + 1);
	for (int i = 1; i <= N; ++i)
	{
		int x, l;
		std::cin >> x >> l;
		graph[i].push_back({x, l, i});
		graph[x].push_back({i, l, i});
	}

	long long ans = 0;

	std::vector<bool> vis(N + 1, false);
	std::vector<bool> is_cycle(N + 1, false);

	for (int i = 1; i <= N; ++i)
	{
		if (vis[i])
			continue;
		int start_cycle = -1;
		std::function<bool(int,int)> find_cycle = [&find_cycle, &graph, &vis, &start_cycle, &is_cycle] (int x, int p) -> bool
		{
			if (vis[x])
				return true;
			vis[x] = true;
			for (auto c : graph[x])
			{
				if (c[2] == p)
					continue;
				if (find_cycle(c[0], c[2]))
				{
					is_cycle[c[0]] = true;
					if (start_cycle == -1)
						start_cycle = c[0];
					return x != start_cycle;
				}
			}
			return false;
		};
		find_cycle(i, -1);

		std::function<std::pair<long long, long long>(int,int)> find_path = [&find_path, &graph, &vis, &is_cycle] (int x, int p) -> std::pair<long long, long long>
		{
			vis[x] = true;
			long long max1 = 0, max2 = 0;
			long long bestc = 0;
			for (auto c : graph[x])
			{
				if (p == c[2] || is_cycle[c[0]])
					continue;
				auto tmp = find_path(c[0], c[2]);
				long long newd = c[1] + tmp.first;
				bestc = std::max(bestc, tmp.second);
				max2 = std::max(max2, newd);
				if (max1 < max2)
					std::swap(max1, max2);
			}
			return {max1, std::max(bestc, max1 + max2)};
		};

		std::vector<long long> circular;
		std::vector<int> circular_edges;

		int last_p = -1;
		int x = start_cycle;
		long long best_local = 0;

		do
		{
			auto tmp = find_path(x, -1);
			best_local = std::max(best_local, tmp.second);
			circular.push_back(tmp.first);
			for (auto c : graph[x])
			{
				if (!is_cycle[c[0]] || c[2] == last_p)
					continue;
				circular_edges.push_back(c[1]);
				last_p = c[2];
				x = c[0];
				break;
			}
		} while (x != start_cycle);

//		for (int j = 0; j < (int) circular.size(); ++j)
//			std::cerr << circular[j] << " (" << circular_edges[j] << ") ";
//		std::cerr << std::endl;

		long long sum = 0;
		long long best1 = -1e18, best2 = -1e18, best3 = -1e18, best4 = -1e18;
		for (int j = 0; j < (int) circular.size(); ++j)
		{
			best3 = std::max(circular[j] + sum + best1, best3);
			best1 = std::max(circular[j] - sum, best1);
			best4 = std::max(circular[j] - sum + best2, best4);
			best2 = std::max(circular[j] + sum, best2);
			sum += circular_edges[j];
		}

		ans += std::max({best_local, best3, sum + best4});
	}
	std::cout << ans << std::endl;
}

• Subtask 1: 33 / 33
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10