| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1048732 | ZanP | 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 "longesttrip.h"
#include <iostream>
#include <vector>
using namespace std;
//bool are_connected(vector<int> A, vector<int> B) { return true; }
void sub1(vector<int> & ans, int n){
ans.resize(n);
for(int i = 0;i<n;i++){ans[i] = i;}
}
void sub2(vector<int>& ans, int n) {
ans.reserve(n);
bool are_last_connected = are_connected({ n - 2 }, { n - 1 });
if (!are_last_connected) { ans.push_back(n - 1); }
ans.push_back(0);
for (int i = 0; i < n - 1; i++) {
if (are_connected({ i }, { i + 1 })) {
ans.push_back(i + 1);
}
else {
if (i == n - 2) { break; }
ans.push_back(i + 2);
ans.push_back(i + 1);
if (!(i == n - 3 || !are_last_connected && i == n-4))ans.push_back(i + 3);
i += 2;
}
}
}
void sub3(vector<int>& ans, int n)
{
ans.reserve(n);
vector<int> path1;
vector<int> path2;
path1.reserve(n);
path2.reserve(n);
path1.push_back(0);
path2.push_back(1);
bool connectTo1=true, connectTo2=true, connectBetween= true;
for(int i = 2; i<n; i++)
{
int a = i;
bool query = are_connected({a}, {path1.back()});
if(query)
{
path1.push_back(a);
connectBetween = true;
}
else if(!connectBetween)
{
path2.push_back(a);
connectBetween = false;
}
else
{
query = are_connected({a}, {path2.back()});
if(query)
{
path2.push_back(a);
connectBetween = false;
}
else
{
if(path2.size() == 1)
{
connectBetween = false;
}
else
{
connectBetween = true;
}
for(int j = path2.size()-1; j >= 0; j--)
{
path1.push_back(path2[j]);
}
path2.clear();
path2.push_back(a);
}
}
}
vector<int> shortPath, longPath;
if(path1.size() > path2.size())
{
longPath = path1;
shortPath = path2;
}
else
{
longPath = path2;
shortPath = path1;
}
bool endsConnected;
if(shortPath.size()==1)
{
endsConnected = are_connected({longPath[0], longPath.back()}, {shortPath[0]});
}
else
{
endsConnected = are_connected({longPath[0], longPath.back()}, {shortPath[0], shortPath.back()});
}
if(endsConnected)
{
if(shortPath.size()==1)
{
if(are_connected({longPath[0]}, {shortPath[0]}))
{
ans.push_back(shortPath[0]);
for (int k=0; k<longPath.size(); k++)
{
ans.push_back(longPath[k]);
}
return;
}
else
{
longPath.push_back(shortPath[0]);
ans = longPath;
return;
}
}
else
{
if(are_connected({longPath[0], longPath.back()}, {shortPath[0]}))
{
if(are_connected({longPath[0]}, {shortPath[0]}))
{
for(int k = longPath.size()-1; k>= 0; k--)
{
ans.push_back(longPath[k]);
}
for(int k= 0; k<shortPath.size(); k++)
{
ans.push_back(shortPath[k]);
}
return;
}
else
{
for(int k = longPath.size()-1; k>= 0; k--)
{
ans.push_back(longPath[k]);
}
for(int k= shortPath.size()-1; k>=0; k--)
{
ans.push_back(shortPath[k]);
}
return;
}
}
else if(are_connected({longPath.back(), longPath.back()}, {shortPath[0]}))
{
for(int k= 0; k<longPath.size(); k++)
{
ans.push_back(longPath[k]);
}
for(int k= 0; k<shortPath.size(); k++)
{
ans.push_back(shortPath[k]);
}
return;
}
else
{
for(int k= 0; k<longPath.size(); k++)
{
ans.push_back(longPath[k]);
}
for(int k= shortPath.size()-1; k>=0; k--)
{
ans.push_back(shortPath[k]);
}
return;
}
}
}
else
{
bool areConnected = are_connected(longPath, shortPath);
if(areConnected)
{
int l=0, r=longPath.size()-1;
while(l!=r)
{
int m = (l+r)>>1;
vector<int> test_data(m-l+1);
for(int k = l;k<=m;k++){
test_data[k-l] = longPath[k];
}
if(are_connected(shortPath, test_data)){
r = m;
}
else{
l = m+1;
}
}
int pos = l;
l = 0, r = shortPath.size()-1;
while(l!=r)
{
int m = (l+r)>>1;
vector<int> test_data(m-l+1);
for(int k = l;k<=m;k++){
test_data[k-l] = shortPath[k];
}
if(are_connected({longPath[pos]}, test_data)){
r = m;
}
else{
l = m+1;
}
}
int pos2 = l;
for(int k = (pos2+1)%shortPath.size();k!=pos2; k = (k+1)%shortPath.size()){
ans.push_back(shortPath[k]);
}
ans.push_back(shortPath[pos2]);
ans.push_back(longPath[pos]);
for(int k = (pos+1)%longPath.size();k!=pos; k = (k+1)%longPath.size()){
ans.push_back(longPath[k]);
}
return;
}
else
{
ans = longPath;
return;
}
}
}
vector<int> longest_trip(int n, int d){
vector<int> ans;
if(d == 3){
sub1(ans, n);
return;
}
if(d == 2){
sub2(ans,n);
return;
}
if(d == 3)
{
sub3(ans, n);
return;
}
return {0, 4, 5 ,2};
}