Submission #856941

#	Time	Username	Problem	Language	Result	Execution time	Memory
856941		mihajanez	Thousands Islands (IOI22_islands)	C++17	100 / 100	112 ms	28556 KiB

islands

#include <bits/stdc++.h>
#include <variant>
#include <vector>
#include <list>
#include <stack>
#include <queue>
using namespace std;


vector<int > construct_journey(
	vector<list<pair<int, int>>> nodes, int fork,
	list<pair<int, int>>c2, list<pair<int, int>>c1_fork_to_cycle_pairs, list<pair<int, int>>c1_cycle_pairs, bool two_cycles) {

	vector<int> journey;

	if (two_cycles) {
		list<int> start_to_fork, c1_fork_to_cycle, c1_cycle, c2_fork_to_cycle, c2_cycle;

		// component2
		int begin_cycle_c2 = c2.back().first;
		c2_cycle.push_front(c2.back().second);
		c2.pop_back();
		while (c2.back().first != begin_cycle_c2) {
			c2_cycle.push_front(c2.back().second);
			c2.pop_back();
		}
		while (c2.back().first != fork) {
			c2_fork_to_cycle.push_front(c2.back().second);
			c2.pop_back();
		}
		while (!c2.empty()) {
			start_to_fork.push_front(c2.back().second);
			c2.pop_back();
		}
		start_to_fork.pop_front();

		// component1
		for (auto& i : c1_fork_to_cycle_pairs) {
			c1_fork_to_cycle.push_back(i.second);
		}
		for (auto& i : c1_cycle_pairs) {
			c1_cycle.push_back(i.second);
		}

		journey.reserve(2 * start_to_fork.size() + 4 * c1_fork_to_cycle.size() + 2 * c1_cycle.size() + 4 * c2_fork_to_cycle.size() + 2 * c2_cycle.size());
		copy(start_to_fork.cbegin(), start_to_fork.cend(), back_inserter(journey));
		copy(c1_fork_to_cycle.cbegin(), c1_fork_to_cycle.cend(), back_inserter(journey));
		copy(c1_cycle.cbegin(), c1_cycle.cend(), back_inserter(journey));
		copy(c1_fork_to_cycle.crbegin(), c1_fork_to_cycle.crend(), back_inserter(journey));
		copy(c2_fork_to_cycle.cbegin(), c2_fork_to_cycle.cend(), back_inserter(journey));
		copy(c2_cycle.cbegin(), c2_cycle.cend(), back_inserter(journey));
		copy(c2_fork_to_cycle.crbegin(), c2_fork_to_cycle.crend(), back_inserter(journey));
		copy(c1_fork_to_cycle.cbegin(), c1_fork_to_cycle.cend(), back_inserter(journey));
		copy(c1_cycle.crbegin(), c1_cycle.crend(), back_inserter(journey));
		copy(c1_fork_to_cycle.crbegin(), c1_fork_to_cycle.crend(), back_inserter(journey));
		copy(c2_fork_to_cycle.cbegin(), c2_fork_to_cycle.cend(), back_inserter(journey));
		copy(c2_cycle.crbegin(), c2_cycle.crend(), back_inserter(journey));
		copy(c2_fork_to_cycle.crbegin(), c2_fork_to_cycle.crend(), back_inserter(journey));
		copy(start_to_fork.crbegin(), start_to_fork.crend(), back_inserter(journey));
	}
	else {
		list<int> start_to_fork, fork_to_join1, fork_to_join2, cycle;

		// component2
		while (c2.front().first != fork) {
			start_to_fork.push_back(c2.front().second);
			c2.pop_front();
		}
		start_to_fork.push_back(c2.front().second);
		start_to_fork.pop_front();
		c2.pop_front();
		for (auto& i : c2) {
			fork_to_join2.push_back(i.second);
		}

		for (auto& i : c1_cycle_pairs) {
			cycle.push_back(i.second);
		}

		int join = c2.back().first;
		// component1
		auto it = c1_fork_to_cycle_pairs.cbegin();
		while (it != c1_fork_to_cycle_pairs.cend() && (*it).first != join) {
			fork_to_join1.push_back((*it++).second);
		}

		// join before the cycle
		if (it != c1_fork_to_cycle_pairs.cend()) {
			fork_to_join1.push_back((*it++).second);
			list<int> join_to_cycle;
			while (it != c1_fork_to_cycle_pairs.cend()) {
				join_to_cycle.push_back((*it++).second);
			}

			journey.reserve(2 * start_to_fork.size() + 2 * fork_to_join1.size() + 2 * fork_to_join2.size() + 4 * join_to_cycle.size() + 2 * cycle.size());
			copy(start_to_fork.cbegin(), start_to_fork.cend(), back_inserter(journey));
			copy(fork_to_join1.cbegin(), fork_to_join1.cend(), back_inserter(journey));
			copy(join_to_cycle.cbegin(), join_to_cycle.cend(), back_inserter(journey));
			copy(cycle.cbegin(), cycle.cend(), back_inserter(journey));
			copy(join_to_cycle.crbegin(), join_to_cycle.crend(), back_inserter(journey));
			copy(fork_to_join1.crbegin(), fork_to_join1.crend(), back_inserter(journey));
			copy(fork_to_join2.cbegin(), fork_to_join2.cend(), back_inserter(journey));
			copy(join_to_cycle.cbegin(), join_to_cycle.cend(), back_inserter(journey));
			copy(cycle.crbegin(), cycle.crend(), back_inserter(journey));
			copy(join_to_cycle.crbegin(), join_to_cycle.crend(), back_inserter(journey));
			copy(fork_to_join2.crbegin(), fork_to_join2.crend(), back_inserter(journey));
			copy(start_to_fork.crbegin(), start_to_fork.crend(), back_inserter(journey));
		}

		// join inside the cycle
		else {
			journey.reserve(2 * start_to_fork.size() + 2 * fork_to_join1.size() + 2 * fork_to_join2.size() + 2 * cycle.size());
			copy(start_to_fork.cbegin(), start_to_fork.cend(), back_inserter(journey));
			copy(fork_to_join1.cbegin(), fork_to_join1.cend(), back_inserter(journey));
			copy(cycle.cbegin(), cycle.cend(), back_inserter(journey));
			copy(fork_to_join1.crbegin(), fork_to_join1.crend(), back_inserter(journey));
			copy(fork_to_join2.cbegin(), fork_to_join2.cend(), back_inserter(journey));
			// rotate the cycle
			while (c1_cycle_pairs.back().first != join) {
				c1_cycle_pairs.push_front(c1_cycle_pairs.back());
				c1_cycle_pairs.pop_back();
				cycle.push_front(cycle.back());
				cycle.pop_back();
			}
			copy(cycle.crbegin(), cycle.crend(), back_inserter(journey));
			copy(fork_to_join2.crbegin(), fork_to_join2.crend(), back_inserter(journey));
			copy(start_to_fork.crbegin(), start_to_fork.crend(), back_inserter(journey));
		}
	}
	return journey;
}


list<pair<int, int>> construct_cycle(vector<list<pair<int, int>>> nodes, int begin_cycle, vector<bool> unavailable_nodes) {
	vector<bool> visited(nodes.size(), false);
	vector<pair<int, int>> predecessors(nodes.size());
	queue<int> bfs_queue;

	visited[begin_cycle] = true;
	bfs_queue.push(begin_cycle);
	while (!bfs_queue.empty()) {
		int last_node = bfs_queue.front();
		bfs_queue.pop();

		for (auto& next_edge : nodes[last_node]) {
			if (!visited[next_edge.first] && !unavailable_nodes[next_edge.first]) {
				visited[next_edge.first] = true;
				bfs_queue.push(next_edge.first);
				predecessors[next_edge.first] = make_pair(last_node, next_edge.second);
			}
			else if (next_edge.first == begin_cycle) {
				list<pair<int, int>> cycle;
				cycle.push_front(make_pair(next_edge.first, next_edge.second));
				while (last_node != begin_cycle) {
					cycle.push_front(make_pair(last_node, predecessors[last_node].second));
					last_node = predecessors[last_node].first;
				}
				return cycle;
			}
		}
	}
	return {};
}


variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
	// pair out_node, out_edge
	vector<list<pair<int, int>>> nodes(N);
	for (auto i = 0; i < U.size(); i++) {
		nodes[U[i]].push_back(make_pair(V[i], i));
	}

	vector<bool>
		visited(nodes.size(), false),
		in_path(nodes.size(), false),
		begin_cycle(nodes.size(), false),
		goal(nodes.size(), false);
	stack<list<pair<int, int>>::const_iterator> dfs_stack;
	list<pair<int, int>> path;
	list<pair<int, int>> c1_fork_to_cycle, c1_cycle;
	bool seek_component2 = false;
	int fork = -1;

	visited[0] = true;
	in_path[0] = true;
	dfs_stack.push(nodes[0].cbegin());
	path.push_back(make_pair(0, -1));
	while (!dfs_stack.empty()) {
		int top_node = path.back().first;

		goal[top_node] = seek_component2;

		// first popped cycle -> found the cycle of component1
		if (!seek_component2 && begin_cycle[top_node]) {
			seek_component2 = true;
			c1_cycle = construct_cycle(nodes, top_node, in_path);
			visited = vector<bool>(nodes.size(), false);
			for (auto& i : c1_cycle) {
				visited[i.first] = true;
				goal[i.first] = true;
			}
			for (auto& i : path) {
				visited[i.first] = true;
			}
		}

		// top_node has more successors
		if (dfs_stack.top() != nodes[path.back().first].cend()) {
			auto& [successor_node, successor_edge] = *dfs_stack.top();
			dfs_stack.top()++;

			// set new fork
			if (seek_component2 && fork == -1) {
				fork = top_node;
			}

			if (!visited[successor_node]) {
				visited[successor_node] = true;
				in_path[successor_node] = true;
				dfs_stack.push(nodes[successor_node].cbegin());
				path.push_back(make_pair(successor_node, successor_edge));
			}
			// found a cycle in component1
			else if (!seek_component2 && in_path[successor_node]) {
				begin_cycle[successor_node] = true;
			}
			// found component2
			else if (goal[successor_node]) {
				path.push_back(make_pair(successor_node, successor_edge));
				// cycle found
				if (in_path[successor_node]) {
					return construct_journey(nodes, fork, path, c1_fork_to_cycle, c1_cycle, true);
				}
				// path to component1 found
				else {
					return construct_journey(nodes, fork, path, c1_fork_to_cycle, c1_cycle, false);
				}
			}
		}
		// top_node has no more successors -> pop it off the stack
		else {
			goal[top_node] = false;
			if (top_node == fork) {
				fork = -1;
			}
			if (seek_component2 && fork == -1) {
				goal[top_node] = true;
				c1_fork_to_cycle.push_front(path.back());
			}

			in_path[top_node] = false;
			dfs_stack.pop();
			path.pop_back();
		}
	}
	return false;
}

Compilation message (stderr)

islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, std::vector<int>, std::vector<int>)':
islands.cpp:169:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |  for (auto i = 0; i < U.size(); i++) {
      |                   ~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 21 / 21
• Subtask 4: 24 / 24
• Subtask 5: 45 / 45