Submission #835036

#	Time	Username	Problem	Language	Result	Execution time	Memory
835036		pavement	Thousands Islands (IOI22_islands)	C++17	0 / 100	32 ms	16156 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define eb emplace_back

using ii = pair<int, int>;

int cur_scc;
vector<int> tp, scc_num, sz_scc, adj_from_0;
vector<bool> vis;
vector<vector<int> > adj, adj_t, adj_scc_t, init;
vector<vector<ii> > adj_2;

void dfs(int u) {
	if (vis[u]) {
		return;
	}
	vis[u] = 1;
	for (auto v : adj_t[u]) {
		dfs(v);
	}
	tp.pb(u);
}

void collect(int u) {
	if (vis[u]) {
		return;
	}
	vis[u] = 1;
	scc_num[u] = cur_scc;
	for (auto v : adj[u]) {
		collect(v);
	}
}

vector<int> dp(int u) {
	vector<int> cur = init[u];
	if ((int)cur.size() > 1) {
		return cur;
	}
	for (auto v : adj_scc_t[u]) {
		auto tmp = dp(v);
		for (int i : tmp) {
			bool in = 0;
			for (int j : cur) {
				if (i == j) {
					in = 1;
					break;
				}
			}
			if (!in) {
				cur.pb(i);
				if ((int)cur.size() > 1) {
					return cur;
				}
			}
		}
	}
	return cur;
}

vector<int> cyc;

int find_cyc(int u, int e = -1) {
	vis[u] = 1;
	for (auto [v, idx] : adj_2[u]) {
		if ((idx ^ 1) != e && vis[v]) {
			cyc.pb(idx);
			//~ cout << u << " --> " << v << endl;
			//~ cout << u << " RET " << v << endl;
			return v;
		}
	}
	for (auto [v, idx] : adj_2[u]) if ((idx ^ 1) != e) {
		int tmp = find_cyc(v, idx);
		if (tmp != -1) {
			if (tmp == -2) {
				//~ path.pb(idx);
			} else {
				cyc.pb(idx);
				if (tmp == u) {
					tmp = -2;
				}
			}
			//~ cout << u << " RET " << tmp << endl;
			return tmp;
		}
	}
	//~ cout << u << " RET " << -1 << endl;
	return -1;
}

vector<int> path;
vector<bool> on_cyc;

bool find_path(int u) {
	vis[u] = 1;
	if (on_cyc[u]) {
		return 1;
	}
	for (auto [v, idx] : adj_2[u]) {
		if (!vis[v] && find_path(v)) {
			path.pb(idx);
			return 1;
		}
	}
	return 0;
}

variant<bool, vector<int> > find_journey(int N, int M, vector<int> U, vector<int> V) {
	vis.resize(N);
	scc_num.resize(N);
	adj.resize(N);
	adj_2.resize(N);
	adj_t.resize(N);
	adj_scc_t.resize(N);
	for (int i = 0; i < M; i++) {
		adj[U[i]].pb(V[i]);
		adj_2[U[i]].eb(V[i], i);
		adj_t[V[i]].pb(U[i]);
	}
	for (int i = 0; i < N; i++) {
		dfs(i);
	}
	reverse(tp.begin(), tp.end());
	fill(vis.begin(), vis.end(), 0);
	for (int i : tp) {
		if (!vis[i]) {
			collect(i);
			cur_scc++;
		}
	}
	sz_scc.resize(cur_scc);
	init.resize(cur_scc);
	for (int i = 0; i < N; i++) {
		sz_scc[scc_num[i]]++;
	}
	for (int i = 0; i < M; i++) {
		if (U[i] == 0 && (int)init[scc_num[V[i]]].size() < 2) {
			init[scc_num[V[i]]].pb(i);
		}
		if (scc_num[U[i]] != scc_num[V[i]]) {			
			adj_scc_t[scc_num[V[i]]].pb(scc_num[U[i]]);
		}
	}
	for (int i = 0; i < cur_scc; i++) {
		auto vec = dp(i);
		if (sz_scc[i] > 1 && (int)vec.size() > 1) {
			fill(vis.begin(), vis.end(), 0);
			int any = -1;
			for (int j = 0; j < N; j++) {
				if (scc_num[j] == i) {
					any = j;
					break;
				}
			}
			assert(any != -1);
			find_cyc(any);
			reverse(cyc.begin(), cyc.end());
			for (auto &i : cyc) {
				if (i == vec[0] || i == vec[1]) {
					i ^= 1;
				}
			}
			on_cyc.resize(N);
			for (auto i : cyc) {
				on_cyc[U[i]] = on_cyc[V[i]] = 1;
			}
			fill(vis.begin(), vis.end(), 0);
			path.clear();
			find_path(V[vec[0]]);
			vector<int> ret;
			path.pb(vec[0]);
			reverse(path.begin(), path.end());
			vector<int> prv_path = path;
			for (auto i : path) {
				ret.pb(i);
			}
			int cur_node = V[ret.back()];
			int st = -1;
			for (int i = 0; i < (int)cyc.size(); i++) {
				if (U[cyc[i]] == cur_node) {
					st = i;
					break;
				}
			}
			assert(st != -1);
			auto nxt = [&](int x) {
				return (x + 1) % (int)cyc.size();
			};
			ret.pb(cyc[st]);
			for (int j = nxt(st); j != st; j = nxt(j)) {
				ret.pb(cyc[j]);
			}
			reverse(path.begin(), path.end());
			for (auto i : path) {
				ret.pb(i);
			}
			fill(vis.begin(), vis.end(), 0);
			path.clear();
			find_path(V[vec[1]]);
			path.pb(vec[1]);
			sort(prv_path.begin(), prv_path.end());
			for (auto &i : path) {
				if (binary_search(prv_path.begin(), prv_path.end(), i)) {
					i ^= 1;
				}
			}
			reverse(path.begin(), path.end());
			for (auto i : path) {
				ret.pb(i);
			}
			cur_node = V[ret.back()];
			st = -1;
			for (int i = 0; i < (int)cyc.size(); i++) {
				if (V[cyc[i]] == cur_node) {
					st = i;
					break;
				}
			}
			assert(st != -1);
			auto prv = [&](int x) {
				if (x == 0) return (int)cyc.size() - 1;
				else return x - 1;
			};
			ret.pb(cyc[st]);
			for (int j = prv(st); j != st; j = prv(j)) {
				ret.pb(cyc[j]);
			}
			reverse(path.begin(), path.end());
			for (auto i : path) {
				ret.pb(i);
			}
			return ret;
		}
	}
	return false;
}

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