Submission #1037330

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037330		42kangaroo	Thousands Islands (IOI22_islands)	C++17	29 / 100	41 ms	7760 KiB

islands

#include "islands.h"

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

using namespace std;

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

void dfs(int n, int &t, g_t &g, vector<bool> &vis, vector<int> &pos) {
	if (vis[n]) return;
	vis[n] = true;
	for (auto [e, nu]: g[n]) {
		dfs(e, t, g, vis, pos);
	}
	pos[n] = t++;
}

void compDfs(int n, int co, g_t &g, vector<int> &comp) {
	if (comp[n] != -1) return;
	comp[n] = co;
	for (auto [e, nu]: g[n]) {
		compDfs(e, co, g, comp);
	}
}

void findDfs(int n, int whi, g_t &g, vector<bool>& vis, vector<int> &res) {
	if (vis[n]) return;
	vis[n] = true;
	if (n == whi) {
		res.push_back(-1);
		return;
	}
	for (auto [e, nu]: g[n]) {
		findDfs(e, whi, g, vis, res);
		if (!res.empty()) return res.push_back(nu);
	}
}

void loopDfs(int n, int whi, g_t &g, vector<bool>& vis, vector<int>& res) {
	if (vis[n]) return;
	vis[n] = true;
	for (auto [e, nu]: g[n]) {
		if (e == whi) return res.push_back(nu);
		loopDfs(e, whi, g, vis, res);
		if (!res.empty()) return res.push_back(nu);
	}
}

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), gT(N);
	for (int i = 0; i < M / 2; ++i) {
		g[U[2 * i]].push_back({V[2 * i], 2 * i});
		gT[V[2 * i]].push_back({U[2 * i], 2 * i});
	}
	vector<bool> vis(N, false);
	vector<int> pos(N, -1);
	int t = 0;
	dfs(0, t, g, vis, pos);
	vector<int> o(N);
	std::iota(o.begin(), o.end(), 0);
	std::sort(o.begin(), o.end(), [&](int l, int r) { return pos[l] > pos[r]; });
	vector<int> comp(N, -1);
	for (int i = 0; i < N; ++i) {
		if (pos[o[i]] == -1) break;
		if (comp[o[i]] != -1) {
			vector<int> resTo, resFor, res;
			std::fill(vis.begin(), vis.end(),false);
			findDfs(0, comp[o[i]], g, vis, resTo);
			std::fill(vis.begin(), vis.end(),false);
			loopDfs(comp[o[i]], comp[o[i]], g, vis, resFor);
			std::reverse(resTo.begin(), resTo.end());
			resTo.pop_back();
			res.reserve(2*resTo.size() + 4*resFor.size());
			res = resTo;
			res.insert(res.end(),resFor.rbegin(), resFor.rend());
			for (int j = resFor.size() - 1; j >= 0; --j) {
				res.push_back(resFor[j] + 1);
			}
			res.insert(res.end(), resFor.begin(), resFor.end());
			for (int j = 0; j < resFor.size(); ++j) {
				res.push_back(resFor[j] + 1);
			}
			std::reverse(resTo.begin(), resTo.end());
			res.insert(res.end(), resTo.begin(), resTo.end());
			return res;
		}
		compDfs(o[i], o[i], gT, comp);
	}
	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:93:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |    for (int j = 0; j < resFor.size(); ++j) {
      |                    ~~^~~~~~~~~~~~~~~

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