Submission #1037683

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037683		kunzaZa183	Thousands Islands (IOI22_islands)	C++17	19.25 / 100	45 ms	76220 KiB

islands

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

const int maxn = 300000, logm = 20;
vector<int> adjlist[maxn];
vector<int> down[maxn], up[maxn];
pair<int, int> arrpii[maxn];
int state[maxn], disc[maxn], depth[maxn];
vector<int> side, extra;

int lca[logm][maxn];

int tim = 0, dep = 0;
void dfs(int cur) {
	state[cur] = 1;
	disc[cur] = tim++;
	depth[cur] = dep;
	for (auto a : adjlist[cur])
		if (state[arrpii[a].second] == 1)
			up[cur].push_back(a);
		else if (state[arrpii[a].second] == 0) {
			lca[0][arrpii[a].second] = cur;
			down[cur].push_back(a);
			dep++;
			dfs(arrpii[a].second);
			dep--;
		}
		else if (disc[arrpii[a].second] > disc[cur])
			extra.push_back(a);
		else
			side.push_back(a);
	state[cur] = 2;
}

struct cmp
{
	bool operator()(int a, int b) const {
		return disc[a] > disc[b];
	}
};
using sidcp = set<int, cmp>*;
vector<int> cyc[maxn];
int highdisc[maxn];

sidcp dfs2(int cur) {
	highdisc[cur] = -1;
	vector<sidcp> vsd;
	for (auto a : down[cur]) {
		vsd.push_back(dfs2(arrpii[a].second));
		if (vsd.back()->count(cur)) {
			highdisc[cur] = cur;
			vsd.back()->erase(cur);
			cyc[cur].push_back(a);
		}
	}
	sidcp maxi = new set<int, cmp>;
	if (!vsd.empty())
		maxi = *max_element(vsd.begin(), vsd.end(),
			[](sidcp a, sidcp b) { return a->size() < b->size(); });
	for (auto a : vsd)
		if (a != maxi)
			for (auto b : *a) maxi->insert(b);
	for (auto a : up[cur]) maxi->insert(arrpii[a].second);
	if (!maxi->empty()) highdisc[cur] = *maxi->begin();
	return maxi;
}

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U,
	vector<int> V) {
	for (int i = 0; i < M; i++) {
		arrpii[i] = { U[i], V[i] };
		adjlist[U[i]].push_back(i);
	}
	dfs(0);
	dfs2(0);

	lca[0][0] = 0;
	for (int i = 1; i < logm; i++)
		for (int j = 0; j < N; j++) lca[i][j] = lca[i - 1][lca[i - 1][j]];

	for (auto a : extra) {
		pair<int, int> pii = arrpii[a];
		if (highdisc[pii.second] != -1)
			if (disc[highdisc[pii.second]] >= disc[pii.first]) {
				return true;
				// good
			}
	}
	for (auto a : side) {
		pair<int, int> pii = arrpii[a];
		if (highdisc[pii.second] != -1) {
			int lci;
			int tmpa = pii.first, tmpb = pii.second;

			if (depth[tmpa] < depth[tmpb]) {
				for (int i = logm - 1; i >= 0; i--)
					if ((1 << i) & (depth[tmpb] - depth[tmpa])) tmpb = lca[i][tmpb];
			}
			else if (depth[tmpa] > depth[tmpb]) {
				for (int i = logm - 1; i >= 0; i--)
					if ((1 << i) & (depth[tmpa] - depth[tmpb])) tmpa = lca[i][tmpa];
			}

			for (int i = logm - 1; i >= 0; i--)
				if (lca[i][tmpa] != lca[i][tmpb]) {
					tmpa = lca[i][tmpa], tmpb = lca[i][tmpb];
				}

			if (tmpa != tmpb) {
				tmpa = lca[0][tmpa], tmpb = lca[0][tmpb];
			}

			lci = tmpa;

			if (disc[lci] <= disc[highdisc[pii.second]]) return true;
		}
	}

	for (int i = 0; i < N; i++)
		if (cyc[i].size() >= 2) return true;

	return false;
}

// int main() {
// 	int N, M;
// 	assert(2 == scanf("%d %d", &N, &M));

// 	std::vector<int> U(M), V(M);
// 	for (int i = 0; i < M; ++i) {
// 		assert(2 == scanf("%d %d", &U[i], &V[i]));
// 	}

// 	std::variant<bool, std::vector<int>> result = find_journey(N, M, U, V);
// 	if (result.index() == 0) {
// 		printf("0\n");
// 		if (std::get<bool>(result)) {
// 			printf("1\n");
// 		}
// 		else {
// 			printf("0\n");
// 		}
// 	}
// 	else {
// 		printf("1\n");
// 		std::vector<int>& canoes = std::get<std::vector<int>>(result);
// 		printf("%d\n", static_cast<int>(canoes.size()));
// 		for (int i = 0; i < static_cast<int>(canoes.size()); ++i) {
// 			if (i > 0) {
// 				printf(" ");
// 			}
// 			printf("%d", canoes[i]);
// 		}
// 		printf("\n");
// 	}
// 	return 0;
// }

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