제출 #150399

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
150399		ummm (#200)	갈라파고스 여행 (FXCUP4_island)	C++17	0 / 100	5117 ms	372324 KiB

island

#include "island.h"

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

const int GAP = 666;

struct UnionFind {
	int n;
	vector<int> uf,si,c;
	UnionFind(int n):n(n),uf(n),si(n,1){
		for(int i=0;i<n;++i) uf[i]=i;
	}
	int find(int x){return x==uf[x]?x:find(uf[x]);}
	bool join(int x, int y, bool keep_track = 1){
		if((x=find(x))==(y=find(y))) return false;
		if(si[x]<si[y]) swap(x,y);
		si[x]+=si[y];uf[y]=x;
		// cout << "Joining " << x << ' ' << y << '\n';
		if(keep_track) c.push_back(y);
		return true;
	}
	void rollback(){
		while(c.size()){
			int x=c.back(); c.pop_back();
			si[uf[x]]-=si[x];uf[x]=x;;
		}
	}
};

vector<UnionFind> UF;
// struct UnionFindPathCompression {
// 	int n;
// 	vector<int> uf;
// 	UnionFindPathCompression(int n):n(n),uf(n){
// 		for(int i=0;i<n;++i) uf[i]=i;
// 	}
// 	int find(int x){return uf[x] = x==uf[x]?x:find(uf[x]);}
// 	bool join(int x, int y){
// 		if((x=find(x))==(y=find(y))) return false;
// 		if(rand()%2) uf[y]=x;
// 		return true;
// 	}
// };
// vector<UnionFindPathCompression> UFPC;

vector<pair<int,int>> edges(300005);
vector<int> pos[100005];

int M, N;

map<int,int> memo[100005];

void Init(int K, vector<int> F, vector<int> S, vector<int> E){
	N = F.size();
	M = S.size();

	edges.resize(M);

	for(int i=0;i<M;++i) edges[M-i-1] = {S[i], E[i]};

	for(int i=0;i<(int)F.size();++i)
		pos[F[i]].push_back(i);

	UnionFind cur(N);

	for(int i=0;i<M;++i){
		if(i%GAP==0) 
			UF.push_back(cur);
		cur.join(edges[i].first, edges[i].second, 0);
	}
	// cout << '\n';
}

int Separate(int A, int B){
	if(A>B) swap(A,B);
	if(memo[A].count(B)) return memo[A][B];

	int bucket = 0, start = 0, ans = -1;
	for(int i=0;i<M;i+=GAP){

		int b = i/GAP;

		for(auto i:pos[A]) UF[b].join(pos[A][0], i, 1);
		for(auto i:pos[B]) UF[b].join(pos[B][0], i, 1);

		if(UF[i/GAP].find(pos[A][0]) == UF[i/GAP].find(pos[B][0])){
			UF[b].rollback();
			break;
		}
		else
			UF[b].rollback();
		start = i, bucket = i/GAP;
	}

	for(auto i:pos[A]) UF[bucket].join(pos[A][0], i, 1);
	for(auto i:pos[B]) UF[bucket].join(pos[B][0], i, 1);

	for(int i=start;i<start+GAP && i<M; ++i){
		UF[bucket].join(edges[i].first, edges[i].second, 1);
		if(UF[bucket].find(pos[A][0]) == UF[bucket].find(pos[B][0])){
			ans = M - i;
			break;
		}
	}
	assert(ans != -1);
	UF[bucket].rollback();
	return memo[A][B] = ans;
}

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