Submission #837377

#	Time	Username	Problem	Language	Result	Execution time	Memory
837377		ymm	Thousands Islands (IOI22_islands)	C++17	55 / 100	45 ms	11084 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < ll(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= ll(l); --x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

namespace s1 {
	std::variant<bool, std::vector<int>> find_journey(
	    int N, int M, std::vector<int> U, std::vector<int> V) {
		vector<int> v[2];
		Loop (i,0,M)
			v[U[i]].push_back(i);
		if (v[0].size() < 2 || v[1].size() < 1)
			return false;
		vector<int> ans = {
			v[0][0], v[1][0], v[0][1], v[0][0], v[1][0], v[0][1],
		};
		return ans;
	}
}

namespace s2 {
	const int N = 512;
	int a[N][N];

	std::variant<bool, std::vector<int>> find_journey(
	    int N, int M, std::vector<int> U, std::vector<int> V) {
		if (N == 2)
			return false;
		Loop (i,0,M)
			a[U[i]][V[i]] = i;
		vector<int> ans = {
			a[0][1], a[1][0], a[0][2], a[2][0], a[1][0], a[0][1], a[2][0], a[0][2],
		};
		return ans;
	}
}

namespace s3 {
	const int N = 100'010;
	vector<pii> A[N];
	bool vis[N];
	bool anc[N];

	vector<int> ans;

	void answer(int v, int p)
	{
		vector<int> vec;
		for (auto [u, e] : A[v]) {
			if (u == p)
				continue;
			vec.push_back(e);
		}
		vector<int> tmp = ans;
		ans.push_back(vec[0]^0);
		ans.push_back(vec[0]^1);
		ans.push_back(vec[1]^0);
		ans.push_back(vec[1]^1);
		ans.push_back(vec[0]^1);
		ans.push_back(vec[0]^0);
		ans.push_back(vec[1]^1);
		ans.push_back(vec[1]^0);
		reverse(tmp.begin(), tmp.end());
		ans.insert(ans.end(), tmp.begin(), tmp.end());
	}

	bool dfs(int v, int p)
	{
		if (A[v].size() - (p != -1) >= 2) {
			answer(v, p);
			return 1;
		}
		for (auto [u, e] : A[v]) {
			if (u == p)
				continue;
			ans.push_back(e);
			if (dfs(u, v))
				return 1;
			ans.pop_back();
		}
		return 0;
	}

	std::variant<bool, std::vector<int>> find_journey(
	    int N, int M, std::vector<int> U, std::vector<int> V) {
		Loop (i,0,M)
			A[U[i]].push_back({V[i], i});
		if (!dfs(0, -1))
			return false;
		return ans;
	}
}

namespace s4 {
	const int N = 100'010;
	vector<pii> A[N];
	bool vis[N];
	bool anc[N];
	int height[N];

	vector<int> ans;

	void answer(int v, int u, int e)
	{
		ans.push_back(e);
		int cnt = height[u] - height[v] + 1;
		int pre = ans.size() - cnt;
		Loop (i,pre,pre+cnt)
			ans.push_back(ans[i]^1);
		LoopR (i,pre,pre+cnt)
			ans.push_back(ans[i]^0);
		LoopR (i,pre,pre+cnt)
			ans.push_back(ans[i]^1);
		LoopR (i,0,pre)
			ans.push_back(ans[i]);
	}

	bool dfs(int v, int h)
	{
		height[v] = h;
		vis[v] = 1;
		anc[v] = 1;
		for (auto [u, e] : A[v]) {
			if (anc[u]) {
				answer(u, v, e);
				return 1;
			}
			if (vis[u])
				continue;
			ans.push_back(e);
			if (dfs(u, h+1))
				return 1;
			ans.pop_back();
		}
		anc[v] = 0;
		return 0;
	}

	std::variant<bool, std::vector<int>> find_journey(
	    int N, int M, std::vector<int> U, std::vector<int> V) {
		for (int i = 0; i < M; i += 2)
			A[U[i]].push_back({V[i], i});
		if (!dfs(0, 0))
			return false;
		return ans;
	}

}

std::variant<bool, std::vector<int>> find_journey(
    int N, int M, std::vector<int> U, std::vector<int> V) {
	if (N == 2)
		return s1::find_journey(N, M, U, V);
	bool is3 = M%2 == 0;
	for (int i = 0; i+2 <= M; i += 2)
		is3 &= U[i] == V[i+1] && U[i+1] == V[i];
	if (is3)
		return s3::find_journey(N, M, U, V);
	bool is4 = M%2 == 0;
	for (int i = 0; i+2 <= M; i += 2)
		is4 &= U[i] == U[i+1] && V[i+1] == V[i];
	if (is4)
		return s4::find_journey(N, M, U, V);
	return s2::find_journey(N, M, U, V);
}

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