| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1048832 | 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
{
ans = longPath;
ans.push_back(shortPath[0]);
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
{
ans = longPath;
for(int k = 0; k<shortPath.size();k++){ans.push_back(shortPath[i]);}
return;
}
}
else if (are_connected({ longPath.back() }, { shortPath.back() }))
{
ans = longPath;
for (int k = shortPath.size()-1; k >= 0; k--)
{
ans.push_back(shortPath[k]);
}
return;
}
else
{
ans = shortPath;
for (int k = 0; k < longPath.size(); k++)
{
ans.push_back(longPath[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 ans;
}
if (d == 2) {
sub2(ans, n);
return ans;
}
if (d == 1)
{
sub3(ans, n);
return ans;
}
return { 0, 4, 5 ,2 };
}
//int main() { return 0; }