Submission #627308

#	Time	Username	Problem	Language	Result	Execution time	Memory
627308		happypotato	Thousands Islands (IOI22_islands)	C++17	10 / 100	130 ms	17100 KiB

islands

#include "islands.h"
#include <variant>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#define rettype variant<bool, vector<int>>
// global
int n, m;
const int mxN = 1e5 + 1;
vector<int> adj[mxN];
int par[mxN];
bool vis[mxN];
int vispos[mxN];
map<pii, int> mp;
vector<int> path;
bool done = false;
int loopstart = -1;
void dfs(int u = 0, int pp = -1) {
	if (done) return;
	vis[u] = true;
	par[u] = pp;
	vispos[u] = path.size();
	path.pb(u);
	for (int v : adj[u]) {
		if (!vis[v]) {
			dfs(v, u);
			if (done) return;
		} else if (v != pp) {
			loopstart = v;
			done = true;
			return;
		}
	}
	path.pop_back();
	vispos[u] = -1;
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
	vector<int> u, v;
	n = N; m = M; u = U; v = V;
	if (n == 2) {
		vector<int> hv[2];
		for (int i = 0; i < m; i++) {
			hv[u[i]].pb(i);
		}
		// cerr << "Checking: " << hv[0].size() << ' ' << hv[1].size() << endl;
		if (hv[0].size() < 2 || hv[1].size() < 1) return false;
		vector<int> ans;
		ans.pb(hv[0][0]);
		ans.pb(hv[1][0]);
		ans.pb(hv[0][1]);
		ans.pb(hv[0][0]);
		ans.pb(hv[1][0]);
		ans.pb(hv[0][1]);
		return ans;
	}
	for (int i = 0; i < m; i++) {
		mp[{u[i], v[i]}] = i;
	}
	for (pair<pii, int> cur : mp) {
		adj[cur.ff.ff].pb(cur.ff.ss);
		// adj[cur.ff.ss].pb(cur.ff.ff);
	}
	dfs();
	if (loopstart == -1) return false;
	// cerr << "loopstart " << loopstart << endl;
	// for (int &cur : path) cerr << cur << ' ';
	// cerr << endl;
	vector<int> ans;
	int looppos = vispos[loopstart];
	int sz = path.size();
	// cerr << "SIZE " << sz << endl;
	for (int i = 0; i < looppos; i++) {
		ans.pb(mp[{path[i], path[i + 1]}]);
	}
	for (int i = looppos; i < sz - 1; i++) {
		ans.pb(mp[{path[i], path[i + 1]}]);
	}
	ans.pb(mp[{path[sz - 1], loopstart}]);
	ans.pb(mp[{loopstart, path[sz - 1]}]);
	for (int i = sz - 2; i >= looppos; i--) {
		ans.pb(mp[{path[i + 1], path[i]}]);
	}
	ans.pb(mp[{path[sz - 1], loopstart}]);
	for (int i = sz - 2; i >= looppos; i--) {
		ans.pb(mp[{path[i], path[i + 1]}]);
	}
	for (int i = looppos; i < sz - 1; i++) {
		ans.pb(mp[{path[i + 1], path[i]}]);
	}
	ans.pb(mp[{loopstart, path[sz - 1]}]);
	for (int i = looppos - 1; i >= 0; i--) {
		ans.pb(mp[{path[i], path[i + 1]}]);
	}
	return ans;
}

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