#include"longesttrip.h"
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
using namespace std;
int n,miss;
int perm[1000];
vector<pair<int,int>>unc; // not connected
set<pair<int,int>>uncs;
map<pair<int,int>,bool>cache;
int qc;
vector<int>per(vector<int>arr){
for(int&i:arr)
i=perm[i];
return arr;
}
bool connected(vector<int>a,vector<int>b){
bool res=are_connected(per(a),per(b));
miss+=!res;
qc++;
return res;
}
bool connected(int a,int b){
if(a>b)
swap(a,b);
if(cache.count({a,b}))
return cache[{a,b}];
cache[{a,b}]=connected(vector<int>({a}),vector<int>({b}));
if(!cache[{a,b}]){
uncs.insert({a,b});
uncs.insert({b,a});
}
return cache[{a,b}];
}
pair<int,int>find_conn(vector<int>v1,vector<int>v2){
int l1=0,r1=(int)v1.size();
while(l1<r1-1){
int mid=(l1+r1)/2;
vector<int>v;
for(int i=l1;i<mid;i++)
v.push_back(v1[i]);
if(connected(v,v2))
r1=mid;
else
l1=mid;
}
int l2=0,r2=(int)v2.size();
while(l2<r2-1){
int mid=(l2+r2)/2;
vector<int>v;
for(int i=l2;i<mid;i++)
v.push_back(v2[i]);
if(connected({v1[l1]},v))
r2=mid;
else
l2=mid;
}
return{v1[l1],v2[l2]};
}
vector<int>merge(vector<int>v1,vector<int>v2){
while(v2.size()){
v1.push_back(v2.back());
v2.pop_back();
}
return v1;
}
bool is_unc(int a,int b){
return uncs.count({a,b});
}
pair<vector<int>,vector<int>>merge(vector<int>v1,vector<int>v2,vector<int>v3){
int num=is_unc(v1.back(),v2.back())+is_unc(v1.back(),v3.back())+is_unc(v2.back(),v3.back());
if(num==2){
if(!is_unc(v1.back(),v2.back()))
return{merge(v1,v2),v3};
if(!is_unc(v2.back(),v3.back()))
return{merge(v3,v2),v1};
if(!is_unc(v1.back(),v3.back()))
return{merge(v1,v3),v2};
}
if(connected(v1.back(),v2.back()))
return{merge(v1,v2),v3};
if(is_unc(v1.back(),v3.back())||connected(v2.back(),v3.back()))
return{merge(v2,v3),v1};
return{merge(v1,v3),v2};
}
vector<int>cyclic_shift(vector<int>arr,int a){
// it ends with a
vector<int>res;
bool b1=false;
for(int i:arr){
if(b1)
res.push_back(i);
if(i==a)
b1=true;
}
bool b2=true;
for(int i:arr){
if(b2)
res.push_back(i);
if(i==a)
b2=false;
}
return res;
}
vector<int>longest_trip(int N,int D){
miss=0;
qc=0;
uncs.clear();
cache.clear();
srand(635748);
n=N;
unc.clear();
for(int i=0;i<n;i++)
perm[i]=i;
for(int i=0;i<n;i++)
swap(perm[i],perm[rand()%n]);
vector<int>arr1={0},arr2;
for(int curr=1;curr<n;curr++){
if(arr2.empty()){
if(connected(curr,arr1.back()))
arr1.push_back(curr);
else
arr2.push_back(curr);
}else{
if(connected(curr,arr1.back()))
arr1.push_back(curr);
else if(connected(curr,arr2.back()))
arr2.push_back(curr);
else{
arr1=merge(arr1,arr2);
arr2={curr};
}
}
}
//cout<<"MISSES: "<<miss<<"\n";
vector<int>res1=arr1;
vector<int>res2=arr2;
if(res2.empty()||!connected(res1,res2)){
if(res1.size()>res2.size())
return per(res1);
else
return per(res2);
}
if(connected({res1.back(),res1[0]},{res2.back(),res2[0]})){
if(connected(res1.back(),res2.back()))
return per(merge(res1,res2));
reverse(res1.begin(),res1.end());
if(connected(res1.back(),res2.back()))
return per(merge(res1,res2));
reverse(res2.begin(),res2.end());
if(connected(res1.back(),res2.back()))
return per(merge(res1,res2));
reverse(res1.begin(),res1.end());
if(connected(res1.back(),res2.back()))
return per(merge(res1,res2));
}
vector<bool>in_res1(n);
for(int i:res1)
in_res1[i]=true;
// both must be cyclical then
pair<int,int>pr={-1,-1};
for(auto[u,v]:unc){
if(in_res1[u]==in_res1[v]){
if(in_res1[u]){
if(connected(res2[0],u)){
pr={u,res2[0]};
}else{
pr={v,res2[0]};
}
}else{
if(connected(res1[0],u)){
pr={res1[0],u};
}else{
pr={res1[0],v};
}
}
break;
}
}
if(pr.first==-1){
//cout<<"FINDING\n";
qc=0;
pr=find_conn(res1,res2);
//cout<<"FOUND IN "<<qc<<"\n";
}
vector<int>r1=cyclic_shift(res1,pr.first);
vector<int>r2=cyclic_shift(res2,pr.second);
return per(merge(r1,r2));
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
2 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
344 KB |
Output is correct |
| 2 |
Correct |
5 ms |
344 KB |
Output is correct |
| 3 |
Correct |
4 ms |
344 KB |
Output is correct |
| 4 |
Correct |
5 ms |
344 KB |
Output is correct |
| 5 |
Correct |
5 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
344 KB |
Output is correct |
| 2 |
Correct |
5 ms |
344 KB |
Output is correct |
| 3 |
Correct |
5 ms |
344 KB |
Output is correct |
| 4 |
Correct |
5 ms |
344 KB |
Output is correct |
| 5 |
Correct |
5 ms |
344 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
344 KB |
invalid array |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
344 KB |
Output is correct |
| 2 |
Correct |
5 ms |
344 KB |
Output is correct |
| 3 |
Correct |
6 ms |
344 KB |
Output is correct |
| 4 |
Correct |
6 ms |
344 KB |
Output is correct |
| 5 |
Correct |
5 ms |
344 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
596 KB |
invalid array |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
344 KB |
Output is correct |
| 2 |
Correct |
5 ms |
344 KB |
Output is correct |
| 3 |
Correct |
5 ms |
344 KB |
Output is correct |
| 4 |
Correct |
5 ms |
344 KB |
Output is correct |
| 5 |
Correct |
4 ms |
344 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
344 KB |
invalid array |
| 7 |
Halted |
0 ms |
0 KB |
- |
