Submission #762469

#	Time	Username	Problem	Language	Result	Execution time	Memory
762469		goodbyehanbyeol	Trip to the Galapagos Islands (FXCUP4_island)	C++17	100 / 100	4813 ms	50036 KiB

island

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

const int NS = (int)2e5 + 4;
int lca[NS][24], pr[NS];
int n, m, ncnt, k;
vector<int> gr[NS], way[NS];
int euler[NS], en, tim[NS], dep[NS];
int eback[NS];

int fd(int x){
	return (x == pr[x] ? x : pr[x] = fd(pr[x]));
}

void Init(int K, std::vector<int> F, std::vector<int> S, std::vector<int> E){
	int n = F.size(), m = S.size(), k = K;
	for(int i = 0; i < NS; ++i){
		pr[i] = i;
	}

	ncnt = n;
	for(int i = m - 1; i >= 0; --i){
		int x = S[i], y = E[i];
		int px = fd(x), py = fd(y);
		if(px == py){
			continue;
		}

		pr[px] = pr[py] = ncnt;
		lca[px][0] = lca[py][0] = ncnt;
		way[ncnt] = {px, py};
		tim[ncnt] = i;
		++ncnt;
	}

	for(int j = 1; j < 20; ++j){
		for(int i = 0; i < ncnt; ++i){
			lca[i][j] = lca[lca[i][j - 1]][j - 1];
		}
	}

	auto dfs = [&](auto&&self, int x)->void{
		euler[x] = ++en;
		eback[en] = x;
		for(auto&nxt:way[x]){
			dep[nxt] = dep[x] + 1;
			self(self, nxt);
		}
	};
	dfs(dfs, ncnt - 1);

	for(int i = 0; i < n; ++i){
		gr[F[i]].push_back(euler[i]);
	}
	for(int i = 0; i < k; ++i){
		sort(gr[i].begin(), gr[i].end());
	}
}

int gettime(int x, int y){
	// cout << "FIND " << x << ' ' << y << endl;
	if(dep[x] > dep[y]){
		swap(x, y);
	}
	for(int i = 19; i >= 0; --i){
		if(dep[y] - (1 << i) >= dep[x]){
			y = lca[y][i];
		}
	}
	if(x == y) return tim[x];
	for(int i = 19; i >= 0; --i){
		if(lca[x][i] != lca[y][i]){
			x = lca[x][i];
			y = lca[y][i];
		}
	}
	return tim[lca[x][0]];
}

map<pair<int, int>, int> save;

int Separate(int A, int B){
	int a = A, b = B;
	if(a > b){
		swap(a, b);
	}
	auto it = save.find(make_pair(a, b));
	if(it != save.end()){
		return it->second;
	}

	int ans = 0;
	if((int)gr[A].size() > (int)gr[B].size()) swap(A, B);
	for(int i = 0; i < (int)gr[A].size(); ++i){
		int pos = lower_bound(gr[B].begin(), gr[B].end(), gr[A][i]) - gr[B].begin();
		if(pos < (int)gr[B].size()){
			ans = max(ans, gettime(eback[gr[A][i]], eback[gr[B][pos]]));
		}
		if(pos){
			--pos;
			ans = max(ans, gettime(eback[gr[A][i]], eback[gr[B][pos]]));
		}
	}

	save[{a, b}] = ans + 1;

	return ans + 1;
}

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