| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 897044 | irmuun | Longest Trip (IOI23_longesttrip) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include "longesttrip.h"
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
vector<int>longest_trip(int N, int D){
vector<int>ans;
if(D==3){
vector<int>ans(N);
iota(all(ans),0);
return ans;
}
if(D==2){
vector<int>ans;
ans.pb(0);
int l=0,r=0;
int x;
for(int i=1;i<N;i++){
if(are_connected({0},{i})==true){
ans.pb(i);
x=i;
r=i;
break;
}
}
for(int i=1;i<N;i++){
if(i!=x){
if(are_connected({l},{i})){
ans.insert(ans.begin(),i);
l=i;
}
else{
ans.pb(i);
r=i;
}
}
}
return ans;
}
vector<int>v,u;
int l0=0,r0=0,l1=1,r1=1;
v.pb(0);
u.pb(1);
for(int i=2;i<N;i++){
if(are_connected({v.back()},{i})==true){
v.pb(i);
}
else if(are_connected({u.back()},{i})==true){
u.pb(i);
}
else{
reverse(all(u));
v.insert(v.end(),all(u));
u={i};
}
}
if(are_connecter(v,u)==false){
if(v.size()>=u.size()){
return v;
}
return u;
}
//now need combine 2 cycles
vector<int>v1=v,u1=u;
while(v1.size()>1){
vector<int>l,r;
for(int i=0;i<v1.size()/2;i++){
l.pb(v1[i]);
}
for(int i=v1.size()/2;i<v1.size();i++){
r.pb(v1[i]);
}
if(are_connected(l,u1)==true){
v1=l;
}
else{
v1=r;
}
}
while(u1.size()>1){
vector<int>l,r;
for(int i=0;i<u1.size()/2;i++){
l.pb(v1[i]);
}
for(int i=u1.size()/2;i<u1.size();i++){
r.pb(v1[i]);
}
if(are_connected(v1,l)==true){
v1=l;
}
else{
v1=r;
}
}
for(int i=0;i<v.size();i++){
if(v[i]==v1[0]){
rotate(v.begin(),v.begin()+i,v.end());
break;
}
}
for(int i=0;i<u.size();i++){
if(u[i]==u1[0]){
rotate(u.begin(),u.begin()+i,u.end());
break;
}
}
reverse(all(u));
v.insert(v.end(),all(u));
return v;
}