#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;
long long n,nn[2],nn2[2],ex[2][100069],ex2[2][100069],sq[100069],zs;
inline bool qr(vector<long long> v,vector<long long> v2)
{
long long i,sz;
vector<int> cv,cv2;
sz=v.size();
for(i=0;i<sz;i++)
{
cv.push_back(v[i]-1);
}
sz=v2.size();
for(i=0;i<sz;i++)
{
cv2.push_back(v2[i]-1);
}
return are_connected(cv,cv2);
}
vector<int> longest_trip(int on,int d)
{
long long i,j,ii,jj,k,l,e,lh,rh,md,zz;
vector<long long> cv,cv2;
vector<int> ret;
n=on;
for(ii=0;ii<2;ii++)
{
nn[ii]=0;
}
for(i=1;i<=n;i+=4)
{
for(ii=0;ii<2;ii++)
{
nn2[ii]=0;
}
for(j=i;j<=min(i+3,n);j++)
{
e=(!nn2[0]||nn2[1]<nn2[0])&&!!nn2[1];
if(!nn2[e])
{
nn2[e]++;
ex2[e][nn2[e]]=i;
}
else
{
k=ex2[e][nn2[e]];
if(qr({i},{k}))
{
nn2[e]++;
ex2[e][nn2[e]]=i;
reverse(ex2[e]+1,ex2[e]+nn2[e]+1);
}
else
{
nn2[!e]++;
ex2[!e][nn2[!e]]=i;
}
}
}
e=!nn[0]&&!!nn[1];
if(!nn[e])
{
for(ii=0;ii<2;ii++)
{
for(j=1;j<=nn2[ii];j++)
{
nn[ii]++;
ex[ii][nn[ii]]=ex2[ii][j];
}
}
}
else
{
k=ex[e][nn[e]];
l=ex2[0][1];
if(!nn[!e])
{
if(qr({k},{l}))
{
for(ii=0;ii<2;i++)
{
for(j=1;j<=nn2[ii];j++)
{
nn[e^ii]++;
ex[e^ii][nn[e^ii]]=ex2[ii][j];
}
}
}
else
{
for(j=nn2[0];j;j--)
{
nn[!e]++;
ex[!e][nn[!e]]=ex2[0][j];
}
if(nn2[1])
{
k=ex[0][nn[0]];
l=ex2[1][1];
e=!qr({k},{l});
for(j=1;j<=nn2[1];j++)
{
nn[e]++;
ex[e][nn[e]]=ex2[1][j];
}
k=ex[0][nn[0]];
l=ex[1][nn[1]];
if(qr({k},{l}))
{
for(j=nn[1];j;j--)
{
nn[0]++;
ex[0][nn[0]]=ex[1][j];
}
nn[1]=0;
}
}
}
}
else
{
e^=!qr({k},{l});
for(j=1;j<=nn2[0];j++)
{
nn[e]++;
ex[e][nn[e]]=ex2[0][j];
}
k=ex[!e][nn[!e]];
l=ex2[1][nn2[1]];
if(qr({k},{l}))
{
for(j=1;j<=nn2[1];j++)
{
nn[!e]++;
ex[!e][nn[!e]]=ex2[1][j];
}
k=ex[0][nn[0]];
l=ex[1][nn[1]];
if(qr({k},{l}))
{
for(j=nn[1];j;j--)
{
nn[0]++;
ex[0][nn[0]]=ex[1][j];
}
nn[1]=0;
}
}
else
{
for(j=nn[!e];j;j--)
{
nn[e]++;
ex[e][nn[e]]=ex[!e][j];
}
nn[!e]=0;
k=ex[e][nn[e]];
l=ex2[1][1];
if(qr({k},{l}))
{
for(j=1;j<=nn2[1];j++)
{
nn[e]++;
ex[e][nn[e]]=ex2[1][j];
}
}
else
{
for(j=nn2[1];j;j--)
{
nn[!e]++;
ex[!e][nn[!e]]=ex2[1][j];
}
}
}
}
}
}
zs=0;
for(i=1;i<=nn[0];i++)
{
cv.push_back(ex[0][i]);
}
for(i=1;i<=nn[1];i++)
{
cv2.push_back(ex[1][i]);
}
if(!nn[0]||!nn[1]||!qr(cv,cv2))
{
e=nn[1]>nn[0];
for(i=1;i<=nn[e];i++)
{
zs++;
sq[zs]=ex[e][i];
}
}
else
{
for(ii=0;ii<2;ii++)
{
k=ex[ii][1];
l=ex[ii][nn[ii]];
if(!qr({k},{l}))
{
break;
}
}
if(ii<2)
{
for(ii=0;ii<2;ii++)
{
k=ex[0][1];
for(jj=0;jj<2;jj++)
{
l=ex[1][1];
if(!zs&&qr({k},{l}))
{
for(i=nn[0];i;i--)
{
zs++;
sq[zs]=ex[0][i];
}
for(i=1;i<=nn[1];i++)
{
zs++;
sq[zs]=ex[1][i];
}
}
reverse(ex[1]+1,ex[1]+nn[1]+1);
}
reverse(ex[0]+1,ex[0]+nn[0]+1);
}
}
else
{
cv2.clear();
for(i=1;i<=nn[1];i++)
{
cv2.push_back(ex[1][i]);
}
for(ii=0;ii<2;ii++)
{
for(lh=1,rh=nn[ii];lh<=rh;)
{
md=(lh+rh)/2;
cv.clear();
for(i=1;i<=md;i++)
{
cv.push_back(ex[ii][i]);
}
if(qr(cv,cv2))
{
zz=md;
rh=md-1;
}
else
{
lh=md+1;
}
}
k=zz;
swap(k,l);
cv2.clear();
for(i=1;i<=zz;i++)
{
cv2.push_back(ex[ii][i]);
}
}
for(i=k+1;i<=nn[0];i++)
{
zs++;
sq[zs]=ex[0][i];
}
for(i=1;i<=k;i++)
{
zs++;
sq[zs]=ex[0][i];
}
for(i=l;i<=nn[1];i++)
{
zs++;
sq[zs]=ex[1][i];
}
for(i=1;i<l;i++)
{
zs++;
sq[zs]=ex[1][i];
}
}
}
for(i=1;i<=zs;i++)
{
ret.push_back(sq[i]-1);
}
return ret;
}
Compilation message
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:271:14: warning: 'zz' may be used uninitialized in this function [-Wmaybe-uninitialized]
271 | for(i=1;i<=zz;i++)
| ~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
non-disjoint arrays |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
non-disjoint arrays |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
non-disjoint arrays |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
2392 KB |
non-disjoint arrays |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
non-disjoint arrays |
| 2 |
Halted |
0 ms |
0 KB |
- |
