Submission #837296

#	Time	Username	Problem	Language	Result	Execution time	Memory
837296		ymm	Thousands Islands (IOI22_islands)	C++17	9.10 / 100	30 ms	8116 KiB

islands

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

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]^0);
	ans.push_back(vec[0]^1);
	ans.push_back(vec[1]^0);
	ans.push_back(vec[1]^1);
	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;
}

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