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 <bits/stdc++.h>
using namespace std;
vector<int> solve_d3(int N, int D) {
vector<int> res(N);
iota(res.begin(), res.end(), 0);
return res;
}
vector<int> solve_d2(int N, int D) {
queue<int> stops;
for (int i = 1; i < N; i++) stops.push(i);
deque<int> trip = {0};
while (stops.size() > 1) {
int next = stops.front(); stops.pop();
int last = trip.back();
if (are_connected({next}, {last})) {
trip.push_back(next);
} else {
trip.push_back(stops.front()); stops.pop();
trip.push_back(next);
}
}
if (stops.size() == 1) {
int next = stops.front();
int last = trip.back();
if (are_connected({next}, {last})) {
trip.push_back(next);
} else {
trip.push_front(stops.front()); stops.pop();
}
}
vector<int> res;
for (int x : trip) res.push_back(x);
return res;
}
bool CACHE[256][256];
bool COMPD[256][256];
bool connected(int x, int y) {
if (x > y) swap(x, y);
if (COMPD[x][y]) return CACHE[x][y];
bool res = are_connected({x}, {y});
CACHE[x][y] = res;
COMPD[x][y] = true;
return res;
}
vector<int> longest_trip(int N, int D) {
if (D == 3) return solve_d3(N, D);
if (D == 2) return solve_d2(N, D);
// resetting the cache
for (auto &row : CACHE) fill(row, row + 256, 0);
for (auto &row : COMPD) fill(row, row + 256, 0);
deque<int> trip = {0};
set<int> stops;
for (int i = 1; i < N; i++) stops.insert(i);
int half = (N / 2) + 1;
int fail = 0;
while (stops.size() > 1) {
for (auto next: stops) {
int a = trip.front(), b = trip.back();
if (connected(a, next)) {
trip.push_front(next);
stops.erase(next);
fail = 0;
continue;
}
if (connected(b, next)) {
trip.push_back(next);
stops.erase(next);
fail = 0;
continue;
}
if (trip.size() >= half) {
break;
}
fail++;
CACHE[a][b] = 1;
CACHE[b][a] = 1;
COMPD[a][b] = 1;
COMPD[b][a] = 1;
if (fail > 100) {
break;
}
}
}
vector<int> res;
for (int x : trip) res.push_back(x);
return res;
}
Compilation message (stderr)
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:88:29: warning: comparison of integer expressions of different signedness: 'std::deque<int, std::allocator<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
88 | if (trip.size() >= half) {
| ~~~~~~~~~~~~^~~~~~~
# | 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... |