Submission #736408

#	Time	Username	Problem	Language	Result	Execution time	Memory
736408		jk410	Thousands Islands (IOI22_islands)	C++17	22.75 / 100	38 ms	5192 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<pair<int, int>> edge[1000];
int deg[1000];
int par[1000];
bool visited[1000];
void dfs(int v) {
	visited[v] = true;
	for (auto i : edge[v]) {
		if (!visited[i.first]) {
			par[i.first] = v;
			dfs(i.first);
		}
	}
}
int f(int x) {
	if (x & 1)
		return x - 1;
	return x + 1;
}
variant<bool, vector<int>> find_journey(int _n, int m, vector<int> u, vector<int> v) {
	n = _n;
	memset(par, -1, sizeof(par));
	for (int i = 0; i < m; i++) {
		edge[u[i]].push_back({ v[i],i });
		deg[u[i]]++;
	}
	visited[0] = true;
	dfs(0);
	int x = -1;
	for (int i = 0; i < n; i++) {
		if (visited[i] && deg[i] > 2)
			x = i;
	}
	if (deg[0] > 1)
		x = 0;
	if (x == -1)
		return false;
	vector<int> p;
	for (int i = x;; i = par[i]) {
		p.push_back(i);
		if (!i)
			break;
	}
	vector<int> ret;
	for (int i = (int)p.size() - 1; i; i--) {
		for (auto j : edge[p[i]]) {
			if (j.first == p[i - 1]) {
				ret.push_back(j.second);
				break;
			}
		}
	}
	int sz = (int)ret.size();
	pair<int, int> e1 = { -1,-1 }, e2 = { -1,-1 };
	for (auto i : edge[x]) {
		if (ret.empty() || ret[sz - 1] != f(i.second)) {
			if (e1.second == -1)
				e1 = { i.second,f(i.second) };
			else if (e2.second == -1)
				e2 = { i.second,f(i.second) };
		}
	}
	ret.push_back(e1.first);
	ret.push_back(e1.second);
	ret.push_back(e2.first);
	ret.push_back(e2.second);
	ret.push_back(e1.second);
	ret.push_back(e1.first);
	ret.push_back(e2.second);
	ret.push_back(e2.first);
	for (int i = sz - 1; i >= 0; i--)
		ret.push_back(ret[i]);
	return ret;
}

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