Submission #1060073

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060073		DorostWef	Thousands Islands (IOI22_islands)	C++17	1.75 / 100	1115 ms	1510652 KiB

islands

#include "islands.h"

#include <variant>
#include <bits/stdc++.h>

#define F first
#define S second
using namespace std;
const int N = 100023;
int par[N];
bool vis[N];
vector <int> a;
int c[N];
int sz[N];
vector <pair <int, int>> g[N], g2[N];
bool f[N], h[N];

void dfs1 (int v, int root) {
	vis[v] = true;
	if (root == 0)
		f[v] = true;
	for (auto [u, id] : g[v]) {
		if (!vis[u]) {
			dfs1 (u, root);
			par[u] = id;
		}
	}
	a.push_back(v);
}

void dfs2 (int v, int root) {
	vis[v] = true;
	c[v] = root;
	sz[root]++;
	for (auto [u, id] : g2[v]) {
		if (!vis[u]) {
			dfs2 (u, root);
		}
	}
}

pair <vector <int>, vector <int>> get (int i, int id) {
	vector <int> v;
	int x = i;
	int y;
	while (true) {
		vis[x] = true;
		int nx = -1;
		int nxi = -1;
		for (auto [u, in] : g[x]) {
			if (h[u]) {
				if (x == i && in == id) {
					nx = u;
					nxi = in;
				} else if (x != i) {
					nx = u;
					nxi = in;
				}
			}
		}
		x = nx;
		if (vis[nx]) {
			y = nx;
			break;
		}
	}
	x = i;
	vector <int> fi, se;
	while (x != y) {
		int nx = -1;
		int nxi = -1;
		for (auto [u, in] : g[x]) {
			if (h[u]) {
				if (x == i && in == id) {
					nx = u;
					nxi = in;
				} else if (x != i) {
					nx = u;
					nxi = in;
				}
			}
		}
		x = nx;
		fi.push_back(nxi);
	}
	x = y;
	int cnt = 0;
	while (x != y || cnt == 0) {
		cnt++;
		int nx = -1;
		int nxi = -1;
		for (auto [u, in] : g[x]) {
			if (h[u]) {
				if (x == i && in == id) {
					nx = u;
					nxi = in;
				} else if (x != i) {
					nx = u;
					nxi = in;
				}
			}
		}
		x = nx;
		se.push_back(nxi);
	}
	return make_pair (fi, se);
}

vector <int> merge (vector <int> a, vector <int> b) {
	for (int x : b)
		a.push_back(x);
	return a;
}

std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {
	int n = N, m = M;
	for (int i = 0; i < m; i++) {
		g2[V[i]].push_back(make_pair (U[i], i));
		g[U[i]].push_back(make_pair (V[i], i));
	}
	for (int i = 0; i < n; i++) {
		if (!vis[i]) {
			dfs1 (i, i);
		}
	}
	reverse (a.begin(), a.end());
	for (int i = 0; i < n; i++)  {
		vis[i] = false;
	}
	for (int i = 0; i < n; i++) {
		if (!vis[a[i]])
			dfs2 (a[i], a[i]);
	}
	for (int i = n - 1; i >= 0; i--) {
		if (sz[c[i]] >= 1)
			h[c[i]] = true;
		for (auto [j, id] : g[i]) {
			h[c[i]] |= h[c[j]];
		}
	}
	for (int i = 0; i < n; i++) {
		h[i] |= h[c[i]];
	}
	for (int i = 0; i < n; i++) {
		if (f[i]) {
			int cnt = 0;
			vector <int> v;
			for (auto [j, id] : g[i]) {
				if (h[j]) {
					cnt++;
					v.push_back(id);
				}
				if (cnt == 2)
					break;
			}
			if (cnt < 2)
				continue;
			vector <int> all, A, B, C, D, E;
			int x = i;
			while (x != 0) {
				A.push_back (par[i]);
				x = U[par[i]] ^ V[par[i]] ^ x;
			}
			reverse (A.begin(), A.end());
			for (int i = 0; i < n; i++) 
				vis[i] = false;
			pair <vector <int>, vector <int>> BB = get (i, v[0]);
			for (int i = 0; i < n; i++) 
				vis[i] = false;
			pair <vector <int>, vector <int>> DD = get (i, v[1]);
			B = BB.F;
			C = BB.S;
			D = DD.F;
			E = DD.S;
			vector <int> nA, nB, nC, nD, nE;
			nA = A;
			nB = B;
			nC = C;
			nD = D;
			nE = E;
			reverse (nA.begin(), nA.end());
			reverse (nB.begin(), nB.end());
			reverse (nC.begin(), nC.end());
			reverse (nD.begin(), nD.end());
			reverse (nE.begin(), nE.end());
			all = merge (all, A);
			all = merge (all, B);
			all = merge (all, C);
			all = merge (all, nB);
			all = merge (all, D);
			all = merge (all, E);
			all = merge (all, nD);
			all = merge (all, B);
			all = merge (all, nC);
			all = merge (all, nB);
			all = merge (all, D);
			all = merge (all, nE);
			all = merge (all, nD);
			all = merge (all, nA);
			return all;
		}
	}
	return false;
}

Compilation message (stderr)

islands.cpp: In function 'std::pair<std::vector<int>, std::vector<int> > get(int, int)':
islands.cpp:49:7: warning: variable 'nxi' set but not used [-Wunused-but-set-variable]
   49 |   int nxi = -1;
      |       ^~~

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