Submission #843369

#	Time	Username	Problem	Language	Result	Execution time	Memory
843369		radoslav11	Longest Trip (IOI23_longesttrip)	C++17	100 / 100	13 ms	1632 KiB

longesttrip

#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <random>
#include <set>
#include <utility>
#include <vector>
#include "longesttrip.h"

using namespace std;

map<pair<vector<int>, vector<int>>, bool> memo;

bool safe_are_connected(vector<int> S_left, vector<int> S_right) {
	if(S_left.size() == 0 || S_right.size() == 0) return false;
	if(memo.count(make_pair(S_left, S_right))) {
		return memo[make_pair(S_left, S_right)];
	}

	bool ret = are_connected(S_left, S_right);
	memo[make_pair(S_left, S_right)] = ret;
	memo[make_pair(S_right, S_left)] = ret;
	return ret;
}

vector<vector<int>> create_adj(
	int N, vector<int> nodes, vector<pair<int, int>> edges
) {
	vector<vector<int>> adj(N);
	vector<bool> in_nodes(N, false);
	for(auto n: nodes) in_nodes[n] = true;

	for(auto e: edges) {
		if(!in_nodes[e.first] || !in_nodes[e.second]) continue;
		adj[e.first].push_back(e.second);
		adj[e.second].push_back(e.first);
	}
	return adj;
}

void add_edge(int u, int v, vector<set<int>> &adj_set) {
	adj_set[u].insert(v);
	adj_set[v].insert(u);
}

void remove_edge(int u, int v, vector<set<int>> &adj_set) {
	adj_set[u].erase(v);
	adj_set[v].erase(u);
}

int only_par(int u, vector<set<int>> &adj_set, int from = -1) {
	assert(adj_set[u].size() <= 2);
	for(auto nei: adj_set[u]) {
		if(nei != from) return nei;
	}
	return -1;
}

void prune_tree(
	int l1, int l2, int l3, vector<int> &leaves, vector<set<int>> &adj_set
) {
	leaves.push_back(l3);

	int u = l1, v = l2;

	while(adj_set[u].size() == 1) {
		int pu = only_par(u, adj_set);
		remove_edge(u, pu, adj_set);
		add_edge(v, u, adj_set);

		v = u;
		u = pu;
	}

	leaves.push_back(v);
}

vector<int> solve_tree(int N, vector<int> nodes, vector<vector<int>> adj) {
	vector<set<int>> adj_set(N);
	for(int i = 0; i < N; i++) {
		adj_set[i] = set<int>(adj[i].begin(), adj[i].end());
	}

	// We assume that the tree is connected here
	vector<int> leaves;
	for(auto node: nodes) {
		if(adj_set[node].size() == 1) {
			leaves.push_back(node);
		}
	}

	mt19937 mt(42);
	while(leaves.size() >= 3) {
		shuffle(leaves.begin(), leaves.end(), mt);
		int l1 = leaves.back();
		leaves.pop_back();
		int l2 = leaves.back();
		leaves.pop_back();
		int l3 = leaves.back();
		leaves.pop_back();

		if(safe_are_connected({l1}, {l2})) {
			prune_tree(l1, l2, l3, leaves, adj_set);
		} else if(safe_are_connected({l1}, {l3})) {
			prune_tree(l1, l3, l2, leaves, adj_set);
		} else {
			// Delta >= 1, means that l2 and l3 are connected
			prune_tree(l2, l3, l1, leaves, adj_set);
		}
	}

	// for(auto node: nodes) {
	// 	cerr << node << "| ";
	// 	for(auto nei: adj_set[node]) {
	// 		cerr << nei << " ";
	// 	}
	// 	cerr << endl;
	// }

	// It's a path
	vector<int> path;
	vector<bool> used(N, false);

	int u = leaves[0];
	int last = -1;
	while(u != -1) {
		path.push_back(u);
		used[u] = true;
		int nlast = u;
		u = only_par(u, adj_set, last);
		last = nlast;
	}

	if(leaves.size() == 2) {
		u = leaves[1];
		vector<int> rev_path;
		while(!used[u]) {
			rev_path.push_back(u);
			int nlast = u;
			u = only_par(u, adj_set, last);
			last = nlast;
		}

		reverse(rev_path.begin(), rev_path.end());
		path.insert(path.end(), rev_path.begin(), rev_path.end());
	}

	return path;
}

pair<int, int> find_one_edge_old(
	vector<int> S_left, vector<int> S_right, mt19937 &mt
) {
	assert(S_left.size() >= 1 && S_right.size() >= 1);

	if(S_left.size() == 1 && S_right.size() == 1) {
		return {S_left[0], S_right[0]};
	}

	shuffle(S_left.begin(), S_left.end(), mt);
	shuffle(S_right.begin(), S_right.end(), mt);

	int mid_left = S_left.size() / 2;
	int mid_right = S_right.size() / 2;

	vector<int> left_left(S_left.begin(), S_left.begin() + mid_left);
	vector<int> left_right(S_left.begin() + mid_left, S_left.end());
	vector<int> right_left(S_right.begin(), S_right.begin() + mid_right);
	vector<int> right_right(S_right.begin() + mid_right, S_right.end());

	if(safe_are_connected(left_left, right_left)) {
		return find_one_edge_old(left_left, right_left, mt);
	} else if(safe_are_connected(left_left, right_right)) {
		return find_one_edge_old(left_left, right_right, mt);
	} else if(safe_are_connected(left_right, right_left)) {
		return find_one_edge_old(left_right, right_left, mt);
	} else {
		return find_one_edge_old(left_right, right_right, mt);
	}
}

pair<int, int> find_one_edge(
	vector<int> S_left, vector<int> S_right, mt19937 &mt
) {
	assert(S_left.size() >= 1 && S_right.size() >= 1);

	if(S_left.size() == 1 && S_right.size() == 1) {
		return {S_left[0], S_right[0]};
	}

	if(S_left.size() < S_right.size()) {
		swap(S_left, S_right);
	}

	shuffle(S_left.begin(), S_left.end(), mt);

	int mid_left = S_left.size() / 2;
	vector<int> left_left(S_left.begin(), S_left.begin() + mid_left);
	vector<int> left_right(S_left.begin() + mid_left, S_left.end());

	if(safe_are_connected(left_left, S_right)) {
		return find_one_edge(left_left, S_right, mt);
	} else {
		return find_one_edge(left_right, S_right, mt);
	}
}

vector<int> longest_trip(int N, int D) {
	assert(D >= 1);
	memo.clear();

	vector<int> comps[2];
	vector<pair<int, int>> edges;

	vector<int> order(N);
	iota(order.begin(), order.end(), 0);

	mt19937 mt(43);
	shuffle(order.begin(), order.end(), mt);

	comps[0].push_back(order[0]);
	int other = 1;
	int tail_0 = order[0];

	while(true) {
		while(other < N && safe_are_connected({tail_0}, {order[other]})) {
			comps[0].push_back(order[other]);
			edges.push_back({tail_0, order[other]});
			tail_0 = order[other];
			other++;
		}

		if(other == N) {
			vector<int> all_nodes(N);
			iota(all_nodes.begin(), all_nodes.end(), 0);
			auto adj = create_adj(N, all_nodes, edges);
			return solve_tree(N, all_nodes, adj);
		} else {
			// Maybe we have two components
			comps[1].push_back(order[other]);
			int tail_1 = order[other];
			other++;

			bool no_link = true;
			while(other < N) {
				vector<pair<int, int>> opts = {{tail_0, 0}, {tail_1, 1}};

				if(mt() % 2 == 0) {
					swap(opts[0], opts[1]);
				}

				int group = opts[0].second, tail = opts[0].first;
				if(safe_are_connected({tail}, {order[other]})) {
					comps[group].push_back(order[other]);
					edges.push_back({tail, order[other]});
					if(group == 0) {
						tail_0 = order[other];
					} else {
						tail_1 = order[other];
					}

					no_link = false;
				} else if(no_link) {
					group = opts[1].second, tail = opts[1].first;
					comps[group].push_back(order[other]);
					edges.push_back({tail, order[other]});
					if(group == 0) {
						tail_0 = order[other];
					} else {
						tail_1 = order[other];
					}
					no_link = true;
				} else {
					if(safe_are_connected({tail_0}, {tail_1})) {
						edges.push_back({tail_0, tail_1});

						// Merge groups
						reverse(comps[1].begin(), comps[1].end());
						comps[0].insert(
							comps[0].end(), comps[1].begin(), comps[1].end()
						);
						comps[1].clear();
						tail_0 = comps[0].back();
						break;
					} else {
						group = opts[1].second, tail = opts[1].first;
						comps[group].push_back(order[other]);
						edges.push_back({tail, order[other]});
						if(group == 0) {
							tail_0 = order[other];
						} else {
							tail_1 = order[other];
						}
						no_link = true;
					}
				}


				other++;
			}

			if(other == N) {
				if(safe_are_connected(comps[0], comps[1])) {
					edges.push_back(find_one_edge(comps[0], comps[1], mt));
					vector<int> all_nodes(N);
					iota(all_nodes.begin(), all_nodes.end(), 0);
					auto adj = create_adj(N, all_nodes, edges);
					return solve_tree(N, all_nodes, adj);
				}

				// Two disjoint paths, so just get the longer one
				if(comps[0].size() < comps[1].size()) swap(comps[0], comps[1]);

				auto adj = create_adj(N, comps[0], edges);
				return solve_tree(N, comps[0], adj);
			}
		}
	}
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 60 / 60