#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
{
if(cyc[l])
{
if(!cyc[x])
{
nx[x].clear();
}
nx2[x].push_back({l,p});
}
cyc[x]=min(cyc[x]+cyc[l],2ll);
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]]&&!cyc[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)
{
if(nx[k][0].empty())
{
return true;
}
l=nx[k][0].fr;
p=nx[k][0].sc;
nn3[ii]++;
ex3[ii][nn3[ii]]=p;
if(l==an[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;
}
Compilation message
islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, std::vector<int>, std::vector<int>)':
islands.cpp:136:16: error: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'struct std::pair<long long int, long long int>'} has no member named 'empty'
136 | if(nx[k][0].empty())
| ^~~~~
