Submission #776602

#	Time	Username	Problem	Language	Result	Execution time	Memory
776602		SanguineChameleon	Thousands Islands (IOI22_islands)	C++17	14.10 / 100	27 ms	6780 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
using namespace std;

const int maxN = 1e5 + 20;
vector<int> adj[maxN];

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
	if (N == 2) {
		vector<int> left;
		vector<int> right;
		for (int i = 0; i < M; i++) {
			if (U[i] == 0) {
				left.push_back(i);
			}
			else {
				right.push_back(i);
			}
		}
		if ((int)left.size() < 2 || right.empty()) {
			return false;
		}
		int A = left[0];
		int B = right[0];
		int C = left[1];
		vector<int> res = {A, B, C, A, B, C};
		return res;
	}
	bool sub3 = (M % 2 == 0);
	bool sub4 = (M % 2 == 0);
	for (int i = 0; i < M; i += 2) {
		sub3 &= (U[i] == V[i + 1] && V[i] == U[i + 1]);
		sub4 &= (U[i] == U[i + 1] && V[i] == V[i + 1]);
	}
	if (sub3) {
		for (int i = 0; i < M; i += 2) {
			adj[U[i]].push_back(V[i]);
			adj[V[i]].push_back(U[i]);
		}
		if (adj[0].empty()) {
			return false;
		}
		if ((int)adj[0].size() >= 2) {
			return true;
		}
		int prv = 0;
		int cur = adj[0][0];
		while (true) {
			if ((int)adj[cur].size() == 1) {
				return false;
			}
			if ((int)adj[cur].size() >= 3) {
				return true;
			}
			int nxt = adj[cur][0] == prv ? adj[cur][1] : adj[cur][0];
			prv = cur;
			cur = nxt;
		}
		return false;
	}
	int A = -1;
	int B = -1;
	int C = -1;
	int D = -1;
	for (int i = 0; i < M; i++) {
		if (U[i] == 0 && V[i] == 1) {
			A = i;
		}
		if (U[i] == 1 && V[i] == 0) {
			B = i;
		}
		if (U[i] == 0 && V[i] == 2) {
			C = i;
		}
		if (U[i] == 2 && V[i] == 0) {
			D = i;
		}
	}
	vector<int> res = {A, B, C, D, B, A, D, C};
	return res;
}

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