#include<bits/stdc++.h>
#include "longesttrip.h"
#define MX 100100
using namespace std;
int n,now,x,y,z,xx,yy,zz,to[MX],g[MX];
vector<int>A,B,ans,ans1,ans2,a[MX];
// queue<int>d;
// bool are_connected(std::vector<int> A, std::vector<int> B)
bool check(int x,int y)
{
A.clear();B.clear();
A.push_back(x);
B.push_back(y);
return are_connected(A,B);
}
bool checkk(int x,vector<int> G)
{
A.clear();
A.push_back(x);
return are_connected(A,G);
}
bool checkkk(int x,vector<int> G)
{
A.clear();
for(int i=0;i<=x;++i)
A.push_back(ans1[i]);
return are_connected(A,G);
}
bool checkkkk(int x,int y)
{
A.clear();
A.push_back(x);
B.clear();
for(int i=0;i<=y;++i)
B.push_back(ans2[i]);
return are_connected(A,B);
}
void dfs(int x,int fa)
{
ans1.push_back(x);
for(int i=0;i<a[x].size();++i)
if(a[x][i]!=fa)
dfs(a[x][i],x);
return;
}
void dfss(int x,int fa)
{
ans2.push_back(x);
for(int i=0;i<a[x].size();++i)
if(a[x][i]!=fa)
dfss(a[x][i],x);
return;
}
int rd(int l,int r)
{
return rand()*rand()%(r-l+1)+l;
}
std::vector<int> longest_trip(int N, int D)
{
n=N;
srand(2019729);
for(int i=0;i<n;++i)
a[i].clear();
for(int i=0;i<n;++i)
g[i]=i;
for(int i=1;i<n;++i)
swap(g[i],g[rd(0,i-1)]);
x=g[0];
to[x]=x;
y=g[1];
to[y]=y;
for(int i=2;i<n;++i){
z=g[i];
to[i]=i;
if(check(x,z)){
a[x].push_back(z);
a[z].push_back(x);
xx=to[x];
zz=to[z];
to[xx]=zz;
to[zz]=xx;
x=xx;
}
else if(check(y,z)){
a[y].push_back(z);
a[z].push_back(y);
yy=to[y];
zz=to[z];
to[yy]=zz;
to[zz]=yy;
y=yy;
}
else{
a[x].push_back(y);
a[y].push_back(x);
xx=to[x];
yy=to[y];
to[xx]=yy;
to[yy]=xx;
x=xx;y=z;
}
}
ans1.clear();
ans2.clear();
ans.clear();
dfs(x,x);
dfss(y,y);
if(!are_connected(ans1,ans2)){
if(ans1.size()>ans2.size())return ans1;
else return ans2;
}
xx=to[x];
yy=to[y];
if(check(x,y)){
for(int i=ans1.size()-1;i>=0;--i)
ans.push_back(ans1[i]);
for(int i=0;i<ans2.size();++i)
ans.push_back(ans2[i]);
}
else if(check(x,yy)){
for(int i=ans1.size()-1;i>=0;--i)
ans.push_back(ans1[i]);
for(int i=ans2.size()-1;i>=0;--i)
ans.push_back(ans2[i]);
}
else if(check(xx,y)){
for(int i=0;i<ans1.size();++i)
ans.push_back(ans1[i]);
for(int i=0;i<ans2.size();++i)
ans.push_back(ans2[i]);
}
else if(check(xx,yy)){
for(int i=0;i<ans1.size();++i)
ans.push_back(ans1[i]);
for(int i=ans2.size()-1;i>=0;--i)
ans.push_back(ans2[i]);
}
else{
int l=0,r=ans1.size()-1;
while(l<r){
int mid=l+r>>1;
if(checkkk(mid,ans2))r=mid;
else l=mid+1;
}
int sav=l;
l=0;r=ans2.size()-1;
while(l<r){
int mid=l+r>>1;
if(checkkkk(ans1[sav],mid))r=mid;
else l=mid+1;
}
int i=sav,j=l;
for(int k=i+1;k<ans1.size();++k)
ans.push_back(ans1[k]);
for(int k=0;k<=i;++k)
ans.push_back(ans1[k]);
for(int k=j;k<ans2.size();++k)
ans.push_back(ans2[k]);
for(int k=0;k<j;++k)
ans.push_back(ans2[k]);
return ans;
}
return ans;
}
Compilation message
longesttrip.cpp: In function 'void dfs(int, int)':
longesttrip.cpp:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(int i=0;i<a[x].size();++i)
| ~^~~~~~~~~~~~
longesttrip.cpp: In function 'void dfss(int, int)':
longesttrip.cpp:50:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int i=0;i<a[x].size();++i)
| ~^~~~~~~~~~~~
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:118:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | for(int i=0;i<ans2.size();++i)
| ~^~~~~~~~~~~~
longesttrip.cpp:128:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | for(int i=0;i<ans1.size();++i)
| ~^~~~~~~~~~~~
longesttrip.cpp:130:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | for(int i=0;i<ans2.size();++i)
| ~^~~~~~~~~~~~
longesttrip.cpp:134:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | for(int i=0;i<ans1.size();++i)
| ~^~~~~~~~~~~~
longesttrip.cpp:142:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
142 | int mid=l+r>>1;
| ~^~
longesttrip.cpp:149:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
149 | int mid=l+r>>1;
| ~^~
longesttrip.cpp:154:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
154 | for(int k=i+1;k<ans1.size();++k)
| ~^~~~~~~~~~~~
longesttrip.cpp:158:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
158 | for(int k=j;k<ans2.size();++k)
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2640 KB |
non-disjoint arrays |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
2640 KB |
Output is correct |
| 2 |
Runtime error |
3 ms |
5200 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
2640 KB |
Output is correct |
| 2 |
Runtime error |
3 ms |
5072 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
2640 KB |
Output is correct |
| 2 |
Runtime error |
4 ms |
5196 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
2640 KB |
Output is correct |
| 2 |
Runtime error |
3 ms |
5072 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
