oj.uz

Submission #776430

# Submission time Handle Problem Language Result Execution time Memory
776430 2023-07-07T21:26:09 Z eliasol Islands (IOI08_islands) C++17
80 / 100
 1179 ms 131072 KB 
#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.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 432 KB Output is correct
2 Correct 2 ms 316 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 828 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1620 KB Output is correct
2 Correct 22 ms 4788 KB Output is correct
3 Correct 13 ms 1876 KB Output is correct
4 Correct 7 ms 1108 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 6600 KB Output is correct
2 Correct 55 ms 9960 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 18028 KB Output is correct
2 Correct 117 ms 24044 KB Output is correct
3 Correct 163 ms 37960 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 32620 KB Output is correct
2 Correct 282 ms 62024 KB Output is correct
3 Correct 305 ms 67608 KB Output is correct
4 Correct 406 ms 95540 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 82528 KB Output is correct
2 Correct 971 ms 131072 KB Output is correct
3 Correct 539 ms 65264 KB Output is correct
4 Correct 592 ms 113676 KB Output is correct
5 Correct 668 ms 114972 KB Output is correct
6 Correct 1179 ms 77524 KB Output is correct
7 Runtime error 629 ms 131072 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 646 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -