Submission #1234441

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234441		nicolo_010	Thousands Islands (IOI22_islands)	C++20	5 / 100	69 ms	12872 KiB

islands

#include <bits/stdc++.h>
#include "islands.h"
using namespace std;
template <typename T>
using v = vector<T>;
using pii = pair<int, int>;
using ll = long long;
#define rep(i, k, n) for (int i = k; i < n; i++)

v<int> anterior;
v<v<int>> adj;
v<int> vis;
v<int> cycle;
int beg;

void dfs(int n, int p=-1) {
	if (beg != -1) return;
	//cout << n << endl;
	vis[n] = 1;
	anterior[n] = p;
	for (auto x : adj[n]) {
		if (beg != -1) return;
		//cout << x << " " << beg << " " << vis[x] << endl;
		if (vis[x] == 1) {
			cycle.clear();
			int u = n;
			beg = x;
			while (anterior[u] != -1) {
				cycle.push_back(u);
				u = anterior[u];
			}
			cycle.push_back(u);
			reverse(cycle.begin(), cycle.end());
			//check validity
			int idx;
			rep(i, 0, (int)cycle.size()) {
				if (cycle[i] == beg) {
					idx = i;
					break;
				}
			}
			
			return;
		}
		if (!vis[x]) {
			dfs(x, n);
		}
	}
	vis[n] = 2;
}

std::variant<bool, v<int>> find_journey(int N, int M, v<int> U, v<int> V) {
	if (N == 2) return false;
	map<pii, int> mp;
	rep(i, 0, M) {
		mp[{U[i], V[i]}] = i;
	}
	return v<int> {mp[{0, 1}], mp[{1, 0}], mp[{0, 2}], mp[{2, 0}], mp[{1, 0}], mp[{0, 1}], mp[{2, 0}], mp[{0, 2}]};
}

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