Submission #148012

#	Time	Username	Problem	Language	Result	Execution time	Memory
148012		imsifile	Trip to the Galapagos Islands (FXCUP4_island)	C++17	100 / 100	2593 ms	22392 KiB

island

#include "island.h"
#include <stdio.h>
#include <algorithm>
#include <memory.h>
using namespace std;
 
const int MINSZ = 200;
int N, K, bcn[100100], maj[100100], mcn;
vector<int> con[100100], mat[505];
 
int par[100100], pv[100100];
int root(int ix){
	if(par[ix]<0) return ix;
	int x=root(par[ix]);
	if(par[ix]!=x) pv[ix]=pv[par[ix]];
	par[ix]=x;
	return x;
}
 
int p2[200200], val[200200], lr[200200][2], vcn;
int poi[100100], pcn, edg[300000], ecn; vector<int> wid[100100];
int rt(int ix){ return p2[ix]<0 ? ix : p2[ix]=rt(p2[ix]); }
void dfs(int ix){
	if(ix<0) return;
	dfs(lr[ix][0]);
	if(val[ix]<0) edg[(1<<17) + ecn++] = -val[ix];
	else poi[pcn++] = val[ix];
	dfs(lr[ix][1]); // dist(s,e) = min(s..e)
}
 
void Init(int K_, vector<int> F, vector<int> S, vector<int> E){
	int M=S.size();
	N=F.size(), K=K_;
	memset(bcn, 0, sizeof(bcn)), mcn=vcn=pcn=ecn=0;
	for(int i=0; i<N; i++) con[F[i]].push_back(i), bcn[F[i]]++, maj[i]=-1;
	for(int i=0; i<K; i++){
		if(bcn[i]<MINSZ) continue;
		maj[i]=mcn;
		for(int j=0; j<=N; j++) par[j]=-1;
		for(int j=M-1; j>=0; j--){
			int s=S[j], e=E[j];
			if(F[s]==i) s=N;
			if(F[e]==i) e=N;
			s=root(s), e=root(e);
			if(s==e) continue;
			if(s==N) par[e]=s, pv[e]=j+1;
			else par[s]=e, pv[s]=j+1;
		}
		mat[mcn].resize(K,0);
		for(int j=0; j<N; j++){
			if(F[j]==i) continue;
			root(j);
			mat[mcn][F[j]] = max(mat[mcn][F[j]], pv[j]);
		}
		mcn++;
	}
	vcn=N;
	for(int i=0; i<N; i++) p2[i]=-1, val[i]=F[i], lr[i][0]=lr[i][1]=-1;
	for(int i=M-1; i>=0; i--){
		int s=rt(S[i]), e=rt(E[i]);
		if(s==e) continue;
		p2[vcn]=-1, val[vcn]=-(i+1), lr[vcn][0]=s, lr[vcn][1]=e;
		p2[s]=p2[e]=vcn++;
	}
	dfs(vcn-1);
	for(int i=(1<<17); --i;){
		if(edg[i*2+1]==0) edg[i]=edg[i*2];
		else edg[i]=min(edg[i*2],edg[i*2+1]);
	}
	for(int i=0; i<N; i++) wid[poi[i]].push_back(i);
}
 
int rmq(int s, int e){
	int mi=1<<20;
	s+=1<<17, e+=1<<17;
	while(s<=e){
		if(s&1) mi=min(mi,edg[s++]);
		if(e%2==0) mi=min(mi,edg[e--]);
		if(s>e) break;
		s>>=1, e>>=1;
	}
	return mi;
}
 
int Separate(int A, int B){
	if(maj[A]>=0) return mat[maj[A]][B];
	if(maj[B]>=0) return mat[maj[B]][A];
	int mx=0, asz=wid[A].size(), bsz=wid[B].size();
	for(int i=0, j=0; i<asz && j<bsz;){
		int s=wid[A][i], e=wid[B][j];
		if(s<e) mx=max(mx,rmq(s,e-1)), i++;
		else swap(s,e), mx=max(mx,rmq(s,e-1)), j++;
	}
	return mx;
}

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