Submission #150078

#	Time	Username	Problem	Language	Result	Execution time	Memory
150078		CHT를 사랑하는 모임 (#200)	Trip to the Galapagos Islands (FXCUP4_island)	C++17	31 / 100	5102 ms	60732 KiB

island

#include "island.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<db,db> pdb;
typedef tuple<int,int,int,int> TP;
typedef vector<vector<ll>> mat;
const int N=3e5+5;
const ll mod=1e9+7;
int n,m,k,a[N],u[N],v[N];
int par[N]; vector<int> g[N];
vector<int> gp[N]; // 소속되었던 그룹 번호들
map<int,int> mp[N];
int fi(int x)
{
	if(par[x]==x) return x;
	return par[x]=fi(par[x]);
}
void un(int x,int y,int t)
{
	x=fi(x); y=fi(y);
	if(g[x].size()<g[y].size()) swap(x,y);
	par[y]=x;
	for(auto &it : g[y]){
		if(mp[x][a[it]]) continue;
		gp[a[it]].push_back(x);
		g[x].push_back(it);
		//cout<<x<<" with "<<y<<" : "<<it<<" , "<<a[it]<<" , "<<x<<" , "<<t<<endl;
		mp[x][a[it]]=t;
	}
}
void Init(int K, std::vector<int> F, std::vector<int> S, std::vector<int> E){
	n=F.size(); m=S.size(); k=K;
	for(int i=0;i<n;i++) a[i+1]=F[i]+1;
	for(int i=0;i<m;i++) u[i+1]=S[i]+1,v[i+1]=E[i]+1;
	for(int i=1;i<=n;i++){
		par[i]=i;
		gp[a[i]].push_back(i);
		g[i].push_back(i);
		mp[i][a[i]]=m+1;
	}
	for(int i=m;i>=1;i--){
		if(fi(u[i])==fi(v[i])) continue;
		un(u[i],v[i],i);
	}
}
int Separate(int a,int b)
{
	a++; b++;
	int ans=1;
	if(gp[a].size()>gp[b].size()) swap(a,b);
	for(auto &g : gp[a]){
		if(!mp[g][b]) continue;
		else ans=max(ans,min(mp[g][a],mp[g][b]));
	}
	return ans;
}

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