Submission #162690

#	Time	Username	Problem	Language	Result	Execution time	Memory
162690		cerberus	Trip to the Galapagos Islands (FXCUP4_island)	C++17	31 / 100	5099 ms	93560 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];
vector<int> in_comp[N], at_islands[N];
vector<pii> roots[N];
bool have[N];

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

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[u][big_finch_id[i]] = 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 lo = 1, hi = m - 1;
		while (lo <= hi) {
			int mid = (lo + hi) / 2;
			bool meet = false;
			vector<int> roots_a;
			for (auto &u : at_islands[A]) {
				auto it = upper_bound(roots[u].begin(), roots[u].end(), make_pair(mid, -1), greater<pii>()) - 1;
				roots_a.pb(it->second);
				have[it->second] = true;
			}
			for (auto &u : at_islands[B]) {
				auto it = upper_bound(roots[u].begin(), roots[u].end(), make_pair(mid, -1), greater<pii>()) - 1;
				if (have[it->second]) {
					meet = true;
					break;
				}
			}
			for (auto &r : roots_a) {
				have[r] = false;
			}
			if (meet) {
				lo = mid + 1;
			} else {
				hi = mid - 1;
			}
		}
		return hi + 1;
	}
	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[u][bid] xor big_finches_done[v][bid]) {
			add_to = (big_finches_done[u][bid] ? v : u);
			big_finches_done[add_to][bid] = 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: 0 / 39
• Subtask 3: 0 / 30