# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1065548 | deera | Longest Trip (IOI23_longesttrip) | C++17 | 7 ms | 600 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 <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;
}
vector<int> longest_trip(int N, int D) {
if (D == 3) return solve_d3(N, D);
if (D == 2) return solve_d2(N, D);
vector<vector<int>> adj;
bool CACHE[300][300];
for (int i = 0; i < N; i++) for (int j = i + 1; j < N; j++) {
if (are_connected({i}, {j})) {
adj[i].push_back(j);
adj[j].push_back(i);
CACHE[i][j] = 1;
CACHE[j][i] = 1;
} else {
CACHE[i][j] = 0;
CACHE[j][i] = 0;
}
}
vector<int> comp;
vector<bool> visited(N, false);
queue<int> q;
q.push(0);
visited[0] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
comp.push_back(u);
for (int v : adj[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
if (comp.size() != N) {
if (comp.size() >= N - comp.size()) {
return comp;
} else {
vector<int> res;
for (int i = 0; i < N; i++) {
if (!visited[i]) res.push_back(i);
}
return res;
}
}
assert(comp.size() == N);
vector<int> best_trip;
deque<int> trip;
vector<bool> used(N, false);
for (int start: comp) {
trip.clear();
fill(used.begin(), used.end(), false);
trip.push_back(start);
used[start] = true;
while (trip.size() < N) {
bool done = false;
if (done == false) for (int v: adj[trip.back()]) if (!used[v]) {
trip.push_back(v);
done = true;
break;
}
if (done == false) for (int v: adj[trip.front()]) if (!used[v]) {
trip.push_front(v);
done = true;
break;
}
if (done == false) break;
}
if (trip.size() == N) {
vector<int> res;
for (int x : trip) res.push_back(x);
return res;
}
if (trip.size() > best_trip.size()) {
best_trip.clear();
for (int x : trip) best_trip.push_back(x);
}
}
return best_trip;
}
Compilation message (stderr)
# | 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... |