Submission #987080

#	Time	Username	Problem	Language	Result	Execution time	Memory
987080		Pyqe	Thousands Islands (IOI22_islands)	C++17	31 / 100	70 ms	57564 KiB

islands

#include <bits/stdc++.h>
#include "islands.h"

using namespace std;

#define mp make_pair
#define fr first
#define sc second

const long long inf=1e18;
long long n,m,nn=0,nn2[2],nn3[2],cnn,dh[100069],an[100069],cyc[100069],ex[100069],ex2[2][100069],ex3[2][100069],cex[100069];
vector<pair<long long,long long>> al[100069],nx[100069],nx2[100069];
vector<long long> vl[100069];
bitset<100069> vtd,vtd2;
pair<long long,long long> pr[100069];
bitset<200069> spc[2];

void dfs(long long x)
{
	long long i,j,sz=al[x].size(),sz2,k,l,p;
	
	vtd[x]=1;
	vtd2[x]=1;
	for(i=0;i<sz;i++)
	{
		l=al[x][i].fr;
		p=al[x][i].sc;
		if(!vtd[l])
		{
			dh[l]=dh[x]+1;
			pr[l]={x,p};
			dfs(l);
		}
		if(vtd2[l])
		{
			if(dh[l]>dh[an[x]]&&!cyc[x])
			{
				an[x]=l;
				nx[x]={{l,p}};
			}
		}
		else
		{
			cyc[x]=min(cyc[x]+cyc[l],2ll);
			if(cyc[l])
			{
				nx2[x].push_back({l,p});
			}
			if(vl[x].empty())
			{
				if(dh[an[l]]>dh[an[x]]&&!cyc[x])
				{
					an[x]=an[l];
					nx[x]={{l,p}};
				}
			}
			else
			{
				if(!cyc[l])
				{
					if(!cyc[x])
					{
						nx[x].clear();
					}
					cyc[x]=min(cyc[x]+1,2ll);
					nx[x].push_back({l,p});
				}
				sz2=vl[x].size();
				for(j=0;j<sz2;j++)
				{
					k=vl[x][j];
					cyc[k]=max(cyc[k],1ll);
				}
				vl[x].clear();
			}
		}
	}
	vtd2[x]=0;
	if(vtd2[an[x]])
	{
		vl[an[x]].push_back(x);
	}
}

variant<bool,vector<int>> find_journey(int on,int om,vector<int> ka,vector<int> la)
{
	long long i,ii,k,l,p,sz,e,kk,ll,rt=0;
	pair<long long,long long> mne={inf,-1};
	vector<int> sq;
	
	n=on;
	m=om;
	for(i=1;i<=m;i++)
	{
		k=ka[i-1]+1;
		l=la[i-1]+1;
		al[k].push_back({l,i});
	}
	dh[0]=-1;
	dfs(1);
	if(cyc[1]!=2)
	{
		return false;
	}
	for(i=1;i<=n;i++)
	{
		if(cyc[i]==2&&dh[i]>dh[rt])
		{
			rt=i;
		}
	}
	for(k=rt;k!=1;k=pr[k].fr)
	{
		p=pr[k].sc;
		nn++;
		ex[nn]=p;
	}
	reverse(ex+1,ex+nn+1);
	for(ii=0;ii<2;ii++)
	{
		for(k=rt;!nx2[k].empty();k=l)
		{
			l=nx2[k].back().fr;
			p=nx2[k].back().sc;
			nx2[k].pop_back();
			nn2[ii]++;
			ex2[ii][nn2[ii]]=p;
		}
		kk=k;
		for(;1;k=l)
		{
			l=nx[k][0].fr;
			p=nx[k][0].sc;
			nn3[ii]++;
			ex3[ii][nn3[ii]]=p;
			if(dh[l]<dh[k])
			{
				break;
			}
		}
		ll=l;
		cnn=0;
		for(k=kk;k!=ll;k=pr[k].fr)
		{
			p=pr[k].sc;
			cnn++;
			cex[cnn]=p;
		}
		reverse(cex+1,cex+cnn+1);
		for(i=1;i<=cnn;i++)
		{
			nn3[ii]++;
			ex3[ii][nn3[ii]]=cex[i];
		}
		for(i=1;i<=n;i++)
		{
			reverse(nx[i].begin(),nx[i].end());
		}
		mne=min(mne,{dh[ll],ii});
	}
	for(ii=0;ii<2;ii++)
	{
		for(i=1;i<=nn3[ii];i++)
		{
			k=ex3[ii][i];
			spc[ii][k]=1;
		}
	}
	for(i=1;i<=nn3[1];i++)
	{
		k=ex3[1][i];
		if(!spc[0][k])
		{
			break;
		}
	}
	if(nn3[0]==nn3[1]&&i>nn3[0])
	{
		for(i=1;i<=nn;i++)
		{
			sq.push_back(ex[i]);
		}
		for(i=1;i<=nn2[0];i++)
		{
			sq.push_back(ex2[0][i]);
		}
		for(i=1;i<=nn3[0];i++)
		{
			sq.push_back(ex3[0][i]);
		}
		for(i=nn2[0];i;i--)
		{
			sq.push_back(ex2[0][i]);
		}
		for(i=1;i<=nn2[1];i++)
		{
			sq.push_back(ex2[1][i]);
		}
		for(i=nn3[1];i;i--)
		{
			sq.push_back(ex3[1][i]);
		}
		for(i=nn2[1];i;i--)
		{
			sq.push_back(ex2[1][i]);
		}
		for(i=nn;i;i--)
		{
			sq.push_back(ex[i]);
		}
	}
	else
	{
		for(i=1;i<=nn3[1];i++)
		{
			k=ex3[1][i];
			if(spc[0][k])
			{
				break;
			}
		}
		if(i<=nn3[1])
		{
			e=mne.sc;
			for(i=1;i<=nn;i++)
			{
				sq.push_back(ex[i]);
			}
			for(i=1;i<=nn2[!e];i++)
			{
				sq.push_back(ex2[!e][i]);
			}
			for(i=1;i<=nn3[!e];i++)
			{
				sq.push_back(ex3[!e][i]);
			}
			for(i=nn2[!e];i;i--)
			{
				sq.push_back(ex2[!e][i]);
			}
			for(i=1;i<=nn2[e];i++)
			{
				sq.push_back(ex2[e][i]);
			}
			for(i=1;i<=nn3[e];i++)
			{
				k=ex3[e][i];
				if(spc[!e][k])
				{
					break;
				}
				sq.push_back(k);
			}
			kk=i;
			for(i=1;ex3[!e][i]!=k;i++);
			for(i=(i+nn3[!e]-2)%nn3[!e]+1;1;i=(i+nn3[!e]-2)%nn3[!e]+1)
			{
				k=ex3[!e][i];
				if(spc[e][k])
				{
					break;
				}
				sq.push_back(k);
			}
			for(i=kk;i<=nn3[e];i++)
			{
				k=ex3[e][i];
				if(!spc[!e][k])
				{
					sq.push_back(k);
				}
			}
			for(i=nn2[e];i;i--)
			{
				sq.push_back(ex2[e][i]);
			}
			for(i=1;i<=nn2[!e];i++)
			{
				k=ex2[!e][i];
				if(spc[e][k])
				{
					break;
				}
				sq.push_back(k);
			}
			if(i<=nn2[!e])
			{
				kk=k;
			}
			else
			{
				kk=ex3[!e][1];
			}
			for(i=1;ex3[e][i]!=kk;i++);
			for(i=(i+nn3[e]-2)%nn3[e]+1;1;i=(i+nn3[e]-2)%nn3[e]+1)
			{
				k=ex3[e][i];
				sq.push_back(k);
				if(k==kk)
				{
					break;
				}
			}
			for(i=nn2[!e];i;i--)
			{
				k=ex2[!e][i];
				if(!spc[e][k])
				{
					sq.push_back(k);
				}
			}
			for(i=nn;i;i--)
			{
				sq.push_back(ex[i]);
			}
		}
		else
		{
			for(i=1;i<=nn;i++)
			{
				sq.push_back(ex[i]);
			}
			for(i=1;i<=nn2[0];i++)
			{
				sq.push_back(ex2[0][i]);
			}
			for(i=1;i<=nn3[0];i++)
			{
				sq.push_back(ex3[0][i]);
			}
			for(i=nn2[0];i;i--)
			{
				sq.push_back(ex2[0][i]);
			}
			for(i=1;i<=nn2[1];i++)
			{
				sq.push_back(ex2[1][i]);
			}
			for(i=1;i<=nn3[1];i++)
			{
				sq.push_back(ex3[1][i]);
			}
			for(i=nn2[1];i;i--)
			{
				sq.push_back(ex2[1][i]);
			}
			for(i=1;i<=nn2[0];i++)
			{
				sq.push_back(ex2[0][i]);
			}
			for(i=nn3[0];i;i--)
			{
				sq.push_back(ex3[0][i]);
			}
			for(i=nn2[0];i;i--)
			{
				sq.push_back(ex2[0][i]);
			}
			for(i=1;i<=nn2[1];i++)
			{
				sq.push_back(ex2[1][i]);
			}
			for(i=nn3[1];i;i--)
			{
				sq.push_back(ex3[1][i]);
			}
			for(i=nn2[1];i;i--)
			{
				sq.push_back(ex2[1][i]);
			}
			for(i=nn;i;i--)
			{
				sq.push_back(ex[i]);
			}
		}
	}
	sz=sq.size();
	for(i=0;i<sz;i++)
	{
		sq[i]--;
	}
	return sq;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 21 / 21
• Subtask 4: 0 / 24
• Subtask 5: 0 / 45