Submission #837348

#	Time	Username	Problem	Language	Result	Execution time	Memory
837348		Sohsoh84	Thousands Islands (IOI22_islands)	C++17	24 / 100	128 ms	30868 KiB

islands

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

using namespace std;

const int MAXN = 1e6 + 10;

#define all(x)		(x).begin(),(x).end()

int n, m, from[MAXN], to[MAXN], level[MAXN];
vector<int> ans, adj[MAXN];
bool edge_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;
}

void dfs(int v) {
	if (flag) return;

	for (int ind : adj[v]) {
		if (flag) return;
		if (edge_vis[ind]) continue;
		if (level[to[ind]] != -1 && level[to[ind]]) {
			flag = true;
			int r = level[v] - level[to[ind]];

			vector<int> cyc;
			while (r--) cyc.push_back(st.top()), st.pop(), ans.pop_back();
			reverse(all(cyc));
			cyc.push_back(ind);

			for (int e : cyc) ans.push_back(e);
			for (int e : cyc) ans.push_back(e ^ 1);
			reverse(all(cyc));
			for (int e : cyc) ans.push_back(e);
			for (int e : cyc) ans.push_back(e ^ 1);
			flag = true;

			return;
		}

		level[to[ind]] = level[v] + 1;
		edge_vis[ind] = true;
		st.push(ind);
		ans.push_back(ind);
		dfs(to[ind]);
		if (flag) return;

		ans.pop_back();
		st.pop();
	}

	level[v] = -1;
}

int cnt_[MAXN];

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];
		from[i + 1] = from[i], to[i + 1] = to[i];
		adj[from[i]].push_back(i);
	}

	level[0] = 1;
	dfs(0);
	if (!flag) return false;
	while (!st.empty()) ans.push_back(st.top()), st.pop();
	
	for (int e : ans)
		cnt_[e]++;

	for (int e : ans)
		assert(cnt_[e] % 2 == 0);

	assert(from[ans.front()] == 0);
	assert(from[ans.back()] == 0);
	return ans;

}

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