Submission #150882

#	Time	Username	Problem	Language	Result	Execution time	Memory
150882		gs14004	Trip to the Galapagos Islands (FXCUP4_island)	C++17	100 / 100	1519 ms	77388 KiB

island

#include "island.h"
#include <bits/stdc++.h>
#define sz(V) ((int)(V).size())
using namespace std;
using pi = pair<int, int>;
const int MAXN = 400005;
 
struct disj{
	int pa[MAXN];
	void init(int n){
		iota(pa, pa + n + 1, 0);
	}
	int find(int x){
		return pa[x] = (pa[x] == x ? x : find(pa[x]));
	}
	bool uni(int p, int q){
		p = find(p);
		q = find(q);
		if(p == q) return 0;
		if(p < q) swap(p, q);
		pa[q] = p; return 1;
	}
}disj;
 
int N, piv;
vector<int> gph[MAXN];
vector<int> V[MAXN];
int din[MAXN], dout[MAXN], cst[MAXN];
int elem[20][MAXN];
 
void dfs(int x){
	for(auto &i : gph[x]){
		din[i] = ++piv;
		elem[0][din[i]] = cst[x];
		dfs(i);
		dout[i] = ++piv;
		elem[0][dout[i]] = cst[x];
	}
}
 
bool cmp(int x, int y){ return din[x] < din[y]; }
 
int lg[MAXN];
void Init(int K, std::vector<int> F, std::vector<int> S, std::vector<int> E){
	for(int i=1; i<MAXN; i++){
		lg[i] = lg[i-1];
		while((2 << lg[i]) <= i) lg[i]++;
	}
	N = sz(F);
	disj.init(2 * N);
	int cnt = N;
	memset(cst, 0x3f, sizeof(cst));
	for(int i=(int)S.size()-1; i>=0; i--){
		int l = disj.find(S[i]);
		int r = disj.find(E[i]);
		if(disj.find(l) != disj.find(r)){
			disj.uni(l, cnt);
			disj.uni(r, cnt);
			cst[cnt] = i + 1;
			gph[cnt].push_back(l);
			gph[cnt].push_back(r);
			cnt++;
		}
	}
	memset(elem, 0x3f, sizeof(elem));
	dfs(cnt - 1);
	for(int i=0; i<N; i++){
		V[F[i]].push_back(i);
	}
	for(int i=0; i<K; i++) sort(V[i].begin(), V[i].end(), cmp);
	for(int i=1; i<20; i++){
		for(int j=1; j<=piv; j++){
			elem[i][j] = elem[i-1][j];
			if(j >= (1 << (i-1))) elem[i][j] = min(elem[i][j], elem[i-1][j - (1<<(i-1))]);
		}
	}
}
 
int QUERY(int x, int y){
	int L = lg[y - x + 1];
	return min(elem[L][y], elem[L][x + (1<<L) - 1]);
}
 
map<pi, int> mp;
 
int Separate(int A, int B){
	if(sz(V[A]) > sz(V[B])) swap(A, B);
	if(mp.find(pi(A, B)) != mp.end()) return mp[pi(A, B)];
	int ret = 0;
	for(auto &i : V[A]){
		auto itr = upper_bound(V[B].begin(), V[B].end(), i, cmp);
		if(itr != V[B].begin()){
			ret = max(ret, QUERY(dout[*prev(itr)], din[i]));
		}
		if(itr != V[B].end()){
			ret = max(ret, QUERY(din[i] + 1, din[*itr]));
		}
	}
	mp[pi(A, B)] = mp[pi(B, A)] = ret;
	return ret;
}

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