Submission #148862

#	Time	Username	Problem	Language	Result	Execution time	Memory
148862		Seishun Buta Yarou wa Yumemiru Shoujo no Yume wo Minai (#200)	Trip to the Galapagos Islands (FXCUP4_island)	C++17	0 / 100	5088 ms	524288 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;
set<int> ss[301111];
typedef bitset<1011> b100;
b100 las[101111];

struct DSU
{
	int S;
	
	struct node
	{
		int p; int las;
	};
	vector<node> dsu;
	
	DSU(int n=0)
	{
		S = n;
		for(int i = 0; i < n; i++)
		{
			node tmp;
			tmp.p = i; tmp.las = -1;
			dsu.pb(tmp);
		}
	}
	
	void reset(int n)
	{
		dsu.clear();
		S = n;
		for(int i = 0; i < n; i++)
		{
			node tmp;
			tmp.p = i; tmp.las = -1;
			dsu.pb(tmp);
		}
	}
	
	int rt(int u)
	{
		if(dsu[u].p == u) return u;
		dsu[u].p = rt(dsu[u].p);
		return dsu[u].p;
	}
	
	void merge(int u, int v)
	{
		u = rt(u); v = rt(v);
		if(u == v) return ;
		if(ss[u].size()<ss[v].size()) swap(u,v);
		dsu[v].p = u; dsu[u].las = v;
		for(int x:ss[v])
		{
			ss[u].insert(x);
		}
		for(int r:ss[u])
		{
			las[v].set(r,1);
		}
	}
	
	bool sameset(int u, int v)
	{
		if(rt(u) == rt(v)) return true;
		return false;
	}
};

struct DSUSimple
{
	int S;
	
	struct node
	{
		int p; int s;
	};
	vector<node> dsu;
	
	DSUSimple(int n=0)
	{
		S = n;
		for(int i = 0; i < n; i++)
		{
			node tmp;
			tmp.p = i; tmp.s=0;
			dsu.pb(tmp);
		}
	}
	
	void reset(int n)
	{
		dsu.clear();
		S = n;
		for(int i = 0; i < n; i++)
		{
			node tmp;
			tmp.p = i; tmp.s=0;
			dsu.pb(tmp);
		}
	}
	
	int rt(int u)
	{
		if(dsu[u].p == u) return u;
		dsu[u].p = rt(dsu[u].p);
		return dsu[u].p;
	}
	
	void merge(int u, int v)
	{
		u = rt(u); v = rt(v);
		if(u == v) return ;
		if(rand()&1) swap(u,v);
		dsu[v].p = u; dsu[u].s|=dsu[v].s;
	}
	
	bool sameset(int u, int v)
	{
		if(rt(u) == rt(v)) return true;
		return false;
	}
};

const int C = 600;
const int M = 300111;
DSU ds[M/C+10];
DSUSimple ds2[M/C+10];
int ini[111111];

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

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++) 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++) 
	{
		ds[i].reset(n); ds2[i].reset(K);
	}
	for(int i=0;i<n;i++)
	{
		ss[i].insert(F[i]);
	}
	for(int i=0;i<m;i++)
	{
		if(i%C==0)
		{
			int cur=i/C;
			for(int j=0;j<n;j++)
			{
				if(ds[cur].rt(j)==j)
				{
					if(ss[j].size()>0)
					{
						int in = *(ss[j].begin());
						for(int v:ss[j])
						{
							ds2[cur].merge(in,v);
							//cerr<<"DS2 "<<cur<<" MERGE "<<in<<' '<<v<<'\n';
						}
					}
				}
			}
			ds[i/C+1]=ds[i/C];
		}
		int u=edges[i].fi; int v=edges[i].se;
		ds[i/C+1].merge(u,v);
	}
	int cur=(m-1)/C+1;
	for(int j=0;j<n;j++)
	{
		if(ds[cur].rt(j)==j)
		{
			if(ss[j].size()>0)
			{
				int in = *(ss[j].begin());
				for(int v:ss[j])
				{
					ds2[cur].merge(in,v);
					//cerr<<"DS2 "<<cur<<" MERGE "<<in<<' '<<v<<'\n';
				}
			}
		}
	}
	memset(ma,-1,sizeof(ma));
}


int Separate(int A, int B)
{
	int id=0;
	for(int i=0;i<M/C+10;i++)
	{
		if(ds2[i].sameset(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;
	vi vv;
	for(int i=curm;i<min(C*(id+1),m);i++)
	{
		int u=edges[i].fi; int v=edges[i].se;
		u=ds[id].rt(u); v=ds[id].rt(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;
		}
	}
	DSUSimple simple(cur+1);
	for(int u:vv)
	{
		if(ds[id].dsu[u].las==-1)
		{
			if(ini[u]==A) st[u]|=1;
			if(ini[u]==B) st[u]|=2;
		}
		else
		{
			int v=ds[id].dsu[u].las;
			if(las[v][A]) st[u]|=1;
			if(las[v][B]) st[u]|=2;
		}
		//if(binary_search(FF[id][A].begin(),FF[id][A].end(),u)) st[u]|=1;
		//if(binary_search(FF[id][B].begin(),FF[id][B].end(),u)) st[u]|=2;
		//cerr<<u<<' '<<x.se<<' '<<st[u]<<endl;
		simple.dsu[ma[u]].s=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=ds[id].rt(u); v=ds[id].rt(v);
		if(u==v) continue;
		int U = ma[u];
		int V = ma[v];
		//cerr<<"MERGE: "<<U<<' '<<V<<'\n';
		simple.merge(U,V);
		U=simple.rt(U);
		if(simple.dsu[U].s==3)
		{
			ans=i; break;
		}
	}
	for(int x:vv)
	{
		st[x]=0; ma[x]=-1;
	}
	return m-ans;
}

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