Submission #1028255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028255		42kangaroo	Thousands Islands (IOI22_islands)	C++17	27.75 / 100	22 ms	5724 KiB

islands

#include "islands.h"

#include <variant>
#include <vector>
#include "bits/stdc++.h"

using namespace std;

using g_t = vector<vector<pair<int,int>>>;

int dfs(int n, int p, g_t& g, vector<bool>& vis, vector<int>& re, vector<int>& oRe) {
	vis[n] = true;
	vector<int> doTh;
	for (auto [ne, nu]: g[n]) {
		if (nu/2 == p/2) continue;
		if (vis[ne]) {
			re.push_back(nu);
			return ne;
		}
		doTh.push_back(nu);
		int res = dfs(ne, nu, g, vis, re, oRe);
		if (re.empty() && oRe.empty()) continue;
		if (!re.empty()) {
			re.push_back(nu);
			if (res == n) {
				re.push_back(-1);
				return -2;
			}
		} else {
			oRe.push_back(nu);
		}
		return res;
	}
	if (doTh.size() > 1) {
		doTh.resize(2);
		oRe = doTh;
	}
	return -2;
}

std::variant<bool, std::vector<int>> find_journey(
		int N, int M, std::vector<int> U, std::vector<int> V) {
	if (N == 2) {
		vector<int> s0, s1;
		for (int i = 0; i < M; ++i) {
			if (U[i] == 0) s0.push_back(i);
			else s1.push_back(i);
		}
		if (s0.size() >= 2 && s1.size() >= 1) {
			return vector<int>{s0[0], s1[0], s0[1], s0[0], s1[0], s0[1]};
		} else return false;
	}
	g_t g(N);
	for (int i = 0; i < M / 2; ++i) {
		g[U[2*i]].push_back({V[2*i], 2*i});
		g[V[2*i]].push_back({U[2*i], 2*i + 1});
	}
	vector<int> intr, oIntr;
	vector<bool> vis(N, false);
	dfs(0, -2, g, vis, intr, oIntr);
	if (intr.empty() && oIntr.empty()) return false;
	vector<int> res;
	if (!intr.empty()) {
		int lim = intr.size() - 1;
		for (int i = intr.size() - 1; intr[i] != -1; --i) {
			res.push_back(intr[i]);
			lim = i - 1;
		}
		for (int i = lim - 1; i >= 0; --i) {
			res.push_back(intr[i]);
		}
		for (int i = 0; i < lim; ++i) {
			res.push_back(intr[i] - (2*(intr[i]%2) - 1));
		}
		for (int i = 0; i < lim; ++i) {
			res.push_back(intr[i]);
		}
		for (int i = lim - 1; i >= 0; --i) {
			res.push_back(intr[i] - (2*(intr[i]%2) - 1));
		}

		for (int i = lim + 1; i < intr.size(); ++i) {
			res.push_back(intr[i]);
		}
	} else {
		for (int i = oIntr.size() - 1; i > 1; --i) {
			res.push_back(oIntr[i]);
		}
		res.push_back(oIntr[0]);
		res.push_back(oIntr[0] - (2*(oIntr[0]%2) - 1));
		res.push_back(oIntr[1]);
		res.push_back(oIntr[1] - (2*(oIntr[1]%2) - 1));
		res.push_back(oIntr[0] - (2*(oIntr[0]%2) - 1));
		res.push_back(oIntr[0]);
		res.push_back(oIntr[1] - (2*(oIntr[1]%2) - 1));
		res.push_back(oIntr[1]);
		for (int i =2; i < oIntr.size(); ++i) {
			res.push_back(oIntr[i]);
		}
	}
	return res;
}

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:82:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   for (int i = lim + 1; i < intr.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~
islands.cpp:97:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |   for (int i =2; i < oIntr.size(); ++i) {
      |                  ~~^~~~~~~~~~~~~~

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