#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 260;
int mark[N];
vector <int> usados;
set <int> s;
vector<int> longest_trip(int N, int D){
deque <int> ans;
ans.push_back(0);
usados.push_back(0);
mark[0] = 1;
for(int i = 1;i < N;i++){
if(are_connected({0}, {i})){
ans.push_back(i);
usados.push_back(i);
mark[i] = 1;
break;
}
}
for(int i = 1;i < N;i++){
if(mark[i])
continue;
s.insert(i);
}
bool aux = true;
while(!s.empty()){
int i = (*s.begin());
if(aux){
vector <int> nao_usados;
for(auto x : s){
if(mark[i])
continue;
nao_usados.push_back(x);
}
if(!are_connected(usados, nao_usados)){
if(usados.size() < nao_usados.size()) swap(usados, nao_usados);
return usados;
}
else{
int l = 0, r = nao_usados.size();
r--;
while(l < r){
int mid = (l+r)/2;
vector <int> v;
for(int i = l;i <= mid;i++){
v.push_back(nao_usados[i]);
}
if(are_connected(v, usados)){
r = mid;
}
else{
l = mid+1;
}
}
int x = nao_usados[l];
l = 0, r = usados.size();
r--;
while(l < r){
int mid = (l+r)/2;
vector <int> v;
for(int i = l;i <= mid;i++){
v.push_back(usados[i]);
}
if(are_connected({x}, v)){
r = mid;
}
else{
l = mid+1;
}
}
//cout << usados[l] << '\n';
while(ans.back() != usados[l]){
int y = ans.back();
ans.pop_back();
ans.push_front(y);
}
ans.push_back(x);
usados.push_back(x);
s.erase(x);
}
}
else{
int x = ans.front(), y = ans.back();
bool a = are_connected({i}, {x}), b = are_connected({i}, {y});
if(a and b){
aux = true;
ans.push_back(i);
}
else if(a){
ans.push_front(i);
}
else if(b){
ans.push_back(i);
}
usados.push_back(i);
s.erase(i);
}
}
vector <int> resposta;
while(!ans.empty()){
resposta.push_back(ans.front());
ans.pop_front();
}
return resposta;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |