Submission #162693

#	Time	Username	Problem	Language	Result	Execution time	Memory
162693		cerberus	Trip to the Galapagos Islands (FXCUP4_island)	C++17	100 / 100	2819 ms	81428 KiB

island

/* cerberus97 - Hanit Banga */

#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include "island.h"

using namespace std;

#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int N = 1e5 + 10, M = 3e5 + 10, S = 150, BIG = N / S + 5;

int n, m;
int par[N], sz[N], max_seen[N];
vector<int> in_comp[N], at_islands[N];
vector<pii> roots[N];

int big_finch_id[N], big_precomp[BIG][N];
vector<int> big_finches;
bool is_big_finch[N], big_finches_done[BIG][N];

int get_root(int u);
void merge(int u, int v, int id, vector<int> &f);

void Init(int k, std::vector<int> f, std::vector<int> eu, std::vector<int> ev) {
	// cout << (sizeof(big_finches_done) + sizeof(big_precomp)) / 1e6 << endl;
	n = f.size(); m = eu.size();
	for (int i = 0; i < n; ++i) {
		par[i] = i;
		sz[i] = 1;
		in_comp[i] = {i};
		roots[i].pb({m, i});
		at_islands[f[i]].pb(i);
	}
	for (int i = 0; i < k; ++i) {
		if (at_islands[i].size() >= S) {
			big_finch_id[i] = big_finches.size();
			big_finches.pb(i);
			is_big_finch[i] = true;
			for (auto &u : at_islands[i]) {
				big_finches_done[big_finch_id[i]][u] = true;
				big_precomp[big_finch_id[i]][f[u]] = m;
			}
		}
	}
	for (int i = m - 1; i >= 0; --i) {
		merge(eu[i], ev[i], i, f);
	}
}

int Separate(int A, int B) {
	if (at_islands[A].size() < at_islands[B].size()) {
		swap(A, B);
	}
	if (is_big_finch[A]) {
		return big_precomp[big_finch_id[A]][B] + 1;
	} else {
		int ans = 1;
		for (auto &u : at_islands[A]) {
			for (auto &p : roots[u]) {
				max_seen[p.second] = max(max_seen[p.second], p.first);
			}
		}
		for (auto &v : at_islands[B]) {
			for (auto &p : roots[v]) {
				auto cand = min(max_seen[p.second], p.first) + 1;
				ans = max(ans, cand);
			}
		}
		for (auto &u : at_islands[A]) {
			for (auto &p : roots[u]) {
				max_seen[p.second] = 0;
			}
		}
		return ans;
	}
	return 0;
}

int get_root(int u) {
	if (u != par[u]) {
		par[u] = get_root(par[u]);
	}
	return par[u];
}

void merge(int u, int v, int id, vector<int> &f) {
	u = get_root(u);
	v = get_root(v);
	if (u == v) {
		return;
	} else if (sz[u] < sz[v]) {
		swap(u, v);
	}
	for (auto &b : big_finches) {
		int add_to = -1, bid = big_finch_id[b];
		if (big_finches_done[bid][u] xor big_finches_done[bid][v]) {
			add_to = (big_finches_done[bid][u] ? v : u);
			big_finches_done[bid][add_to] = true;
			for (auto &w : in_comp[add_to]) {
				big_precomp[bid][f[w]] = max(big_precomp[bid][f[w]], id);
			}
		}
	}
	par[v] = u;
	sz[u] += sz[v];
	for (auto &w : in_comp[v]) {
		in_comp[u].pb(w);
		roots[w].pb({id, u});
	}
	in_comp[v].clear();
}

• Subtask 1: 31 / 31
• Subtask 2: 39 / 39
• Subtask 3: 30 / 30