Submission #843311

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
843311	2023-09-03T22:21:35 Z	radoslav11	Longest Trip (IOI23_longesttrip)	C++17	85 / 100	13 ms	1208 KB

longesttrip

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

using namespace std;

bool safe_are_connected(vector<int> S_left, vector<int> S_right) {
	if(S_left.size() == 0 || S_right.size() == 0) return false;
	return are_connected(S_left, S_right);
}

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(are_connected({l1}, {l2})) {
			prune_tree(l1, l2, l3, leaves, adj_set);
		} else if(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(
	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(left_left, right_left, mt);
	} else if(safe_are_connected(left_left, right_right)) {
		return find_one_edge(left_left, right_right, mt);
	} else if(safe_are_connected(left_right, right_left)) {
		return find_one_edge(left_right, right_left, mt);
	} else {
		return find_one_edge(left_right, right_right, mt);
	}
}

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

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

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

	mt19937 mt(42);
	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 && 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++;

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

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

				bool try_other = false;

				int group = opts[0].second, tail = opts[0].first;
				if(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];
					}
					try_other = true;
				} 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];
					}
				}

				group = opts[1].second, tail = opts[1].first;
				if(try_other && are_connected({tail}, {order[other]})) {
					edges.push_back({tail, order[other]});

					// 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();
					other++;
					break;
				}

				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 / 0.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	500 KB	Output is correct
2	Correct	2 ms	448 KB	Output is correct

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	344 KB	Output is correct
2	Correct	5 ms	344 KB	Output is correct
3	Correct	5 ms	344 KB	Output is correct
4	Correct	5 ms	344 KB	Output is correct
5	Correct	5 ms	344 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	344 KB	Output is correct
2	Correct	8 ms	344 KB	Output is correct
3	Correct	5 ms	344 KB	Output is correct
4	Correct	5 ms	344 KB	Output is correct
5	Correct	6 ms	344 KB	Output is correct
6	Correct	11 ms	344 KB	Output is correct
7	Correct	6 ms	344 KB	Output is correct
8	Correct	6 ms	596 KB	Output is correct
9	Correct	5 ms	596 KB	Output is correct
10	Correct	6 ms	600 KB	Output is correct
11	Correct	6 ms	856 KB	Output is correct
12	Correct	5 ms	344 KB	Output is correct
13	Correct	5 ms	344 KB	Output is correct

Subtask #3

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	344 KB	Output is correct
2	Correct	9 ms	344 KB	Output is correct
3	Correct	5 ms	344 KB	Output is correct
4	Correct	5 ms	600 KB	Output is correct
5	Correct	5 ms	600 KB	Output is correct
6	Correct	11 ms	344 KB	Output is correct
7	Correct	6 ms	344 KB	Output is correct
8	Correct	5 ms	344 KB	Output is correct
9	Correct	5 ms	600 KB	Output is correct
10	Correct	6 ms	344 KB	Output is correct
11	Correct	5 ms	596 KB	Output is correct
12	Correct	5 ms	344 KB	Output is correct
13	Correct	5 ms	344 KB	Output is correct
14	Correct	10 ms	344 KB	Output is correct
15	Correct	9 ms	344 KB	Output is correct
16	Correct	9 ms	344 KB	Output is correct
17	Correct	6 ms	344 KB	Output is correct
18	Correct	7 ms	344 KB	Output is correct
19	Correct	6 ms	856 KB	Output is correct
20	Correct	6 ms	856 KB	Output is correct
21	Correct	6 ms	344 KB	Output is correct
22	Correct	5 ms	520 KB	Output is correct
23	Correct	5 ms	768 KB	Output is correct
24	Correct	5 ms	600 KB	Output is correct
25	Correct	11 ms	344 KB	Output is correct
26	Correct	9 ms	344 KB	Output is correct
27	Correct	6 ms	344 KB	Output is correct
28	Correct	7 ms	344 KB	Output is correct
29	Correct	8 ms	344 KB	Output is correct
30	Correct	7 ms	440 KB	Output is correct
31	Correct	7 ms	440 KB	Output is correct
32	Correct	8 ms	432 KB	Output is correct
33	Correct	7 ms	636 KB	Output is correct
34	Correct	7 ms	344 KB	Output is correct
35	Correct	6 ms	344 KB	Output is correct
36	Correct	6 ms	444 KB	Output is correct
37	Correct	8 ms	604 KB	Output is correct
38	Correct	7 ms	604 KB	Output is correct
39	Correct	9 ms	604 KB	Output is correct
40	Correct	11 ms	600 KB	Output is correct
41	Correct	7 ms	344 KB	Output is correct
42	Correct	7 ms	600 KB	Output is correct
43	Correct	7 ms	600 KB	Output is correct
44	Correct	9 ms	704 KB	Output is correct
45	Correct	13 ms	344 KB	Output is correct
46	Correct	11 ms	344 KB	Output is correct
47	Correct	10 ms	760 KB	Output is correct
48	Correct	9 ms	344 KB	Output is correct
49	Correct	9 ms	344 KB	Output is correct
50	Correct	7 ms	692 KB	Output is correct
51	Correct	9 ms	440 KB	Output is correct
52	Correct	9 ms	440 KB	Output is correct
53	Correct	8 ms	696 KB	Output is correct
54	Correct	8 ms	636 KB	Output is correct
55	Correct	9 ms	600 KB	Output is correct
56	Correct	7 ms	960 KB	Output is correct
57	Correct	7 ms	600 KB	Output is correct
58	Correct	9 ms	700 KB	Output is correct
59	Correct	10 ms	604 KB	Output is correct
60	Correct	8 ms	700 KB	Output is correct
61	Correct	8 ms	600 KB	Output is correct
62	Correct	8 ms	444 KB	Output is correct
63	Correct	8 ms	872 KB	Output is correct
64	Correct	9 ms	680 KB	Output is correct

Subtask #4

45.0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	344 KB	Output is correct
2	Correct	6 ms	344 KB	Output is correct
3	Correct	5 ms	344 KB	Output is correct
4	Correct	5 ms	600 KB	Output is correct
5	Correct	7 ms	600 KB	Output is correct
6	Correct	12 ms	344 KB	Output is correct
7	Correct	8 ms	600 KB	Output is correct
8	Correct	6 ms	460 KB	Output is correct
9	Correct	5 ms	472 KB	Output is correct
10	Correct	6 ms	600 KB	Output is correct
11	Correct	5 ms	600 KB	Output is correct
12	Correct	6 ms	600 KB	Output is correct
13	Correct	7 ms	344 KB	Output is correct
14	Correct	11 ms	344 KB	Output is correct
15	Correct	9 ms	600 KB	Output is correct
16	Correct	8 ms	344 KB	Output is correct
17	Correct	7 ms	600 KB	Output is correct
18	Correct	7 ms	344 KB	Output is correct
19	Correct	7 ms	1112 KB	Output is correct
20	Correct	7 ms	856 KB	Output is correct
21	Correct	11 ms	344 KB	Output is correct
22	Correct	9 ms	504 KB	Output is correct
23	Correct	9 ms	344 KB	Output is correct
24	Correct	10 ms	344 KB	Output is correct
25	Correct	8 ms	600 KB	Output is correct
26	Correct	8 ms	444 KB	Output is correct
27	Correct	8 ms	436 KB	Output is correct
28	Correct	11 ms	436 KB	Output is correct
29	Correct	7 ms	600 KB	Output is correct
30	Correct	7 ms	344 KB	Output is correct
31	Correct	7 ms	344 KB	Output is correct
32	Correct	9 ms	344 KB	Output is correct
33	Correct	13 ms	344 KB	Output is correct
34	Correct	9 ms	344 KB	Output is correct
35	Correct	10 ms	600 KB	Output is correct
36	Correct	11 ms	344 KB	Output is correct
37	Correct	9 ms	460 KB	Output is correct
38	Correct	11 ms	440 KB	Output is correct
39	Correct	8 ms	440 KB	Output is correct
40	Correct	8 ms	724 KB	Output is correct
41	Correct	9 ms	476 KB	Output is correct
42	Correct	10 ms	600 KB	Output is correct
43	Correct	6 ms	344 KB	Output is correct
44	Correct	6 ms	604 KB	Output is correct
45	Correct	5 ms	924 KB	Output is correct
46	Correct	6 ms	344 KB	Output is correct
47	Correct	5 ms	452 KB	Output is correct
48	Correct	8 ms	444 KB	Output is correct
49	Correct	10 ms	856 KB	Output is correct
50	Correct	7 ms	604 KB	Output is correct
51	Correct	8 ms	868 KB	Output is correct
52	Correct	8 ms	696 KB	Output is correct
53	Correct	7 ms	868 KB	Output is correct
54	Correct	8 ms	696 KB	Output is correct
55	Correct	9 ms	444 KB	Output is correct
56	Correct	8 ms	700 KB	Output is correct
57	Correct	8 ms	612 KB	Output is correct
58	Correct	7 ms	604 KB	Output is correct
59	Correct	8 ms	600 KB	Output is correct
60	Correct	7 ms	448 KB	Output is correct
61	Correct	8 ms	600 KB	Output is correct
62	Correct	7 ms	528 KB	Output is correct
63	Correct	7 ms	444 KB	Output is correct
64	Correct	9 ms	1208 KB	Output is correct
65	Correct	9 ms	868 KB	Output is correct
66	Correct	9 ms	696 KB	Output is correct
67	Partially correct	9 ms	600 KB	Output is partially correct
68	Partially correct	8 ms	700 KB	Output is partially correct
69	Partially correct	9 ms	600 KB	Output is partially correct
70	Partially correct	9 ms	1120 KB	Output is partially correct
71	Correct	7 ms	600 KB	Output is correct
72	Correct	8 ms	680 KB	Output is correct
73	Partially correct	9 ms	448 KB	Output is partially correct
74	Partially correct	8 ms	616 KB	Output is partially correct
75	Partially correct	7 ms	600 KB	Output is partially correct
76	Partially correct	8 ms	600 KB	Output is partially correct
77	Correct	8 ms	448 KB	Output is correct
78	Correct	8 ms	856 KB	Output is correct
79	Partially correct	8 ms	604 KB	Output is partially correct
80	Partially correct	8 ms	704 KB	Output is partially correct
81	Partially correct	8 ms	600 KB	Output is partially correct
82	Partially correct	9 ms	600 KB	Output is partially correct