Submission #149860

#	Time	Username	Problem	Language	Result	Execution time	Memory
149860		Seishun Buta Yarou wa Yumemiru Shoujo no Yume wo Minai (#200)	Trip to the Galapagos Islands (FXCUP4_island)	C++17	31 / 100	4712 ms	307424 KiB

island

#include "island.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef unsigned long long ull;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;
int n,m;
vector<ii> edges;
int ini[111111];

const int C = 405;
const int M = 300111;
int dsu[M/C+10][101111];

int st[333333];
int ma[333333];
int inve[333333];

void reset(int id, int n)
{
	for(int i = 0; i < n; i++)
	{
		dsu[id][i]=i;
	}
}
	
int rt(int id, int u)
{
	if(dsu[id][u] == u) return u;
	return (dsu[id][u] = rt(id, dsu[id][u]));
}
	
void merge(int id, int u, int v)
{
	u = rt(id,u); v = rt(id,v);
	if(u == v) return ;
	if(rand()&1) swap(u,v);
	dsu[id][v] = u;
}
	
bool sameset(int id, int u, int v)
{
	if(rt(id,u) == rt(id,v)) return true;
	return false;
}

int dsu2[111111];
int s2[111111];

void reset(int n)
{
	for(int i = 0; i < n; i++)
	{
		dsu2[i]=i; s2[i]=0;
	}
}
	
int rt(int u)
{
	if(dsu2[u] == u) return u;
	dsu2[u] = rt(dsu2[u]);
	return dsu2[u];
}
	
void merge(int u, int v)
{
	u = rt(u); v = rt(v);
	if(u == v) return ;
	if(rand()&1) swap(u,v);
	dsu2[v] = u; s2[u]|=s2[v];
}



void Init(int K, std::vector<int> F, std::vector<int> S, std::vector<int> E)
{
	n = F.size();
	m = S.size();
	for(int i=0;i<n;i++)
	{
		inve[F[i]]=i;
	}
	for(int i=0;i<n;i++) ini[i]=F[i];
	for(int i=0;i<m;i++)
	{
		edges.pb({S[i],E[i]});
	}
	reverse(edges.begin(),edges.end());
	for(int i=0;i<M/C+10;i++) 
	{
		reset(i,n);
	}
	for(int i=0;i<m;i++)
	{
		if(i%C==0)
		{
			for(int j=0;j<n;j++)
			{
				dsu[i/C+1][j]=dsu[i/C][j];
			}
		}
		int u=edges[i].fi; int v=edges[i].se;
		merge(i/C+1,u,v);
	}
	memset(ma,-1,sizeof(ma));
}


int Separate(int A, int B)
{
	int id=0;
	A=inve[A]; B=inve[B];
	for(int i=0;i<M/C+10;i++)
	{
		if(sameset(i,A,B))
		{
			id=i-1; break;
		}
	}
	//start from ds[id]
	//until curm-1 A and B arent connected
	int curm = C*id;
	int cur=-1;
	A=rt(id,A); B=rt(id,B);
	vi vv;
	for(int i=curm;i<min(C*(id+1),m);i++)
	{
		int u=edges[i].fi; int v=edges[i].se;
		u=rt(id,u); v=rt(id,v);
		if(u==v) continue;
		if(ma[u]==-1) 
		{
			vv.pb(u); ma[u]=++cur;
		}
		if(ma[v]==-1) 
		{
			vv.pb(v); ma[v]=++cur;
		}
	}
	reset(cur+1);
	for(int u:vv)
	{
		if(u==A) st[u]|=1; 
		if(u==B) st[u]|=2;
		s2[ma[u]]=st[u];
		//cerr<<x.se<<' '<<st[u]<<endl;
	}
	int ans = 0;
	for(int i=curm;i<min(C*(id+1),m);i++)
	{
		int u=edges[i].fi; int v=edges[i].se;
		u=rt(id,u); v=rt(id,v);
		if(u==v) continue;
		int U = ma[u];
		int V = ma[v];
		//cerr<<"MERGE: "<<U<<' '<<V<<'\n';
		merge(U,V);
		U=rt(U);
		if(s2[U]==3)
		{
			ans=i; break;
		}
	}
	for(int x:vv)
	{
		st[x]=0; ma[x]=-1;
	}
	return m-ans;
}

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