Submission #837284

#	Time	Username	Problem	Language	Result	Execution time	Memory
837284		Sohsoh84	Thousands Islands (IOI22_islands)	C++17	21 / 100	40 ms	29620 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 10;

int n, m, from[MAXN], to[MAXN];
vector<int> ans, adj[MAXN];
bool vis[MAXN], flag = false;
stack<int> st;

inline int f(int ind, int v) {
	return from[ind] ^ to[ind] ^ v;
}

inline int find_edge(int ind, int u) {
	return from[ind] == u ? ind : ind + 1;
}

inline void seven(int a, int b) {
	ans.push_back(a);
	ans.push_back(a ^ 1);
	ans.push_back(b);
	ans.push_back(b ^ 1);
	ans.push_back(a ^ 1);
	ans.push_back(a);
	ans.push_back(b ^ 1);
	ans.push_back(b);
}

void dfs(int v) {
	vector<int> poss;
	for (int ind : adj[v])
		if (!vis[ind])
			poss.push_back(ind);

	if (poss.empty()) return;
	if (int(poss.size()) == 1) {
		int ind = find_edge(poss[0], v);
		vis[poss[0]] = true;
		st.push(ind);
		ans.push_back(ind);
		dfs(f(ind, v));
	} else {
		flag = true;
		seven(find_edge(poss[0], v), find_edge(poss[1], v));
	}
}

variant<bool, vector<int>> find_journey(int n_, int m_, vector<int> U_, vector<int> V_) {
	n = n_;
	m = m_;
	for (int i = 0; i < m; i += 2) {
		from[i] = U_[i], to[i] = V_[i];
		adj[from[i]].push_back(i), adj[to[i]].push_back(i);
	}

	dfs(0);
	if (!flag) return false;
	while (!st.empty()) ans.push_back(st.top()), st.pop();
	return ans;

}

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