| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 842568 | 2023-09-03T03:58:56 Z | irmuun | Longest Trip (IOI23_longesttrip) | C++17 | 0 ms | 0 KB |
#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()
bool con[256][256];
bool are_connected(vector<int>a,vector<int>b){
bool ok=false;
for(auto x:a){
for(auto y:b){
ok|=con[x][y];
}
}
return ok;
}
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=1;i<N;i++){
if(are_connected({l0,r0},{i})==false){
if(are_connected({l0},{i})==true){
l0=i;
v.insert(v.begin(),i);
}
else{
v.pb(i);
r0=i;
}
}
else{
if(are_connected({r0},{r1})==true){
reverse(all(u));
v.insert(v.end(),all(u));
u.clear();
u.pb(i);
r0=v.back();
l1=i;
r1=i;
}
else{
r1=i;
u.pb(i);
}
}
}
if(v.size()>=u.size()){
return v;
}
return u;
}