#include <vector>
std::vector<int> longest_trip(int N, int D);
bool are_connected(std::vector<int> A, std::vector<int> B);
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
int n;
bool adj[256][256];
vector<int> conn[256];
void makePath(vector<int>& nodes, vector<int>& out);
vector<int> secondary;
void makePaths(vector<int>& nodes, vector<int>& primary) {
secondary.clear();
if (nodes.size() <= 1) {
for (int x: nodes) {
primary.push_back(x);
}
return;
}
vi g1;
vector<bool> mask(n, true);
for (int x: nodes) {
mask[x] = false;
}
queue<int> q;
q.push(nodes[0]);
while (!q.empty()) {
auto t = q.front(); q.pop();
if (mask[t]) continue;
g1.push_back(t);
mask[t] = true;
for (int c: conn[t]) {
q.push(c);
}
}
if (g1.size() == nodes.size()) {
makePath(nodes, primary);
secondary.clear();
} else {
for (int x: g1) {
primary.push_back(x);
}
for (int x: nodes) {
if (!mask[x]) {
secondary.push_back(x);
}
}
}
}
#define MIDDLE 0
#define INTER 1
#define UPPER 2
#define LOWER 3
void makePath(vector<int>& nodes, vector<int>& res) {
if (nodes.size() <= 2) {
for (int x: nodes) {
res.push_back(x);
}
}
vector<int> nodeTypes(n, -1);
int middleNode = nodes[0];
nodeTypes[middleNode] = MIDDLE;
vi lowerNodes, interNodes, upperNodes;
for (int x: nodes) {
if (nodeTypes[x] == -1 && !adj[x][middleNode]) {
lowerNodes.push_back(x);
nodeTypes[x] = LOWER;
}
}
for (int x: nodes) {
if (nodeTypes[x] != -1) continue;
bool bruh = false;
for (int y: lowerNodes) {
if (adj[x][y]) {
bruh = true;
break;
}
}
if (bruh) {
interNodes.push_back(x);
nodeTypes[x] = INTER;
} else {
upperNodes.push_back(x);
nodeTypes[x] = UPPER;
}
}
if (lowerNodes.size() == 0) {
makePaths(upperNodes, res);
res.push_back(middleNode);
for (int x: secondary) {
res.push_back(x);
}
} else if (lowerNodes.size() == 1) {
for (int x: upperNodes) {
res.push_back(x);
}
res.push_back(middleNode);
makePaths(interNodes, res);
res.push_back(lowerNodes[0]);
for (int x: secondary) {
res.push_back(x);
}
} else {
for (int x: upperNodes) {
res.push_back(x);
}
res.push_back(middleNode);
makePaths(interNodes, res);
int n1 = res.back();
if (secondary.empty()) {
int start;
for (int x:lowerNodes) {
if (adj[x][n1]) {
start = x;
break;
}
}
res.push_back(start);
for (int x:lowerNodes) {
if (x != start) res.push_back(x);
}
} else {
int n2 = secondary.front();
int a, b;
vector<int> a1, a2;
for (int x: lowerNodes) {
if (adj[n1][x]) {
a1.push_back(x);
}
if (adj[n2][x]) {
a2.push_back(x);
}
}
if (a1.size() > 1 && a2.size() > 1) {
a = a1[0];
b = a2[0] == a ? a2[1] : a2[0];
} else if (a2.size() > 1) {
a = a1[0];
b = a2[0] == a ? a2[1] : a2[0];
} else if (a1.size() > 1) {
b = a2[0];
a = a1[0] == b ? a1[1] : a1[0];
} else {
a = a1[0];
b = a2[0];
}
out:
res.push_back(a);
for (int x: lowerNodes) {
if (x != a && x != b) {
res.push_back(x);
}
}
res.push_back(b);
for (int x: secondary) {
res.push_back(x);
}
}
}
}
/*
1
5 1
0
1 1
0 1 0
1 0 0 1
*/
vector<int> longest_trip(int N, int D) {
n = N;
memset(adj, false, sizeof(adj));
for (int i = 0; i < N; i++) {
conn[i].clear();
}
vi allNodes;
for (int i = 0; i < N; i++) {
allNodes.push_back(i);
for (int j = i+1; j < N; j++) {
if (are_connected({i}, {j})) {
adj[i][j] = adj[j][i] = true;
conn[i].push_back(j);
conn[j].push_back(i);
}
}
}
vector<int> primary;
makePaths(allNodes, primary);
if (primary.size() > secondary.size()) {
return primary;
} else {
return secondary;
}
}
#ifdef BRUH
static inline constexpr int maxNumberOfCalls = 32640;
static inline constexpr int maxTotalNumberOfCalls = 150000;
static inline constexpr int maxTotalNumberOfLandmarksInCalls = 1500000;
static int call_counter = 0;
static int total_call_counter = 0;
static int landmark_counter = 0;
static int C, N, D;
static std::vector<std::vector<int>> U;
static std::vector<bool> present;
static inline void protocol_violation(std::string message)
{
printf("Protocol Violation: %s\n", message.c_str());
exit(0);
}
bool are_connected(std::vector<int> A, std::vector<int> B)
{
++call_counter;
++total_call_counter;
if (call_counter > maxNumberOfCalls || total_call_counter > maxTotalNumberOfCalls)
{
protocol_violation("too many calls");
}
int nA = A.size(), nB = B.size();
landmark_counter += nA + nB;
if (landmark_counter > maxTotalNumberOfLandmarksInCalls)
{
protocol_violation("too many elements");
}
if (nA == 0 || nB == 0)
{
protocol_violation("invalid array");
}
for (int i = 0; i < nA; ++i)
{
if (A[i] < 0 || N <= A[i])
{
protocol_violation("invalid array");
}
if (present[A[i]])
{
protocol_violation("invalid array");
}
present[A[i]] = true;
}
for (int i = 0; i < nA; ++i)
{
present[A[i]] = false;
}
for (int i = 0; i < nB; ++i)
{
if (B[i] < 0 || N <= B[i])
{
protocol_violation("invalid array");
}
if (present[B[i]])
{
protocol_violation("invalid array");
}
present[B[i]] = true;
}
for (int i = 0; i < nB; ++i)
{
present[B[i]] = false;
}
for (int i = 0; i < nA; ++i)
{
for (int j = 0; j < nB; ++j)
{
if (A[i] == B[j])
{
protocol_violation("non-disjoint arrays");
}
}
}
for (int i = 0; i < nA; ++i)
{
for (int j = 0; j < nB; ++j)
{
if (U[std::max(A[i], B[j])][std::min(A[i], B[j])] == 1)
{
return true;
}
}
}
return false;
}
int main()
{
assert(1 == scanf("%d", &C));
int maximumCalls = 0;
for (int c = 0; c < C; ++c)
{
call_counter = 0;
assert(2 == scanf("%d %d", &N, &D));
present.assign(N, false);
U.resize(N);
for (int i = 1; i < N; ++i)
{
U[i].resize(i);
for (int j = 0; j < i; ++j)
{
assert(1 == scanf("%d", &U[i][j]));
}
}
for (int i = 2; i < N; ++i)
{
for (int j = 1; j < i; ++j)
{
for (int k = 0; k < j; ++k)
{
if (U[i][j] + U[i][k] + U[j][k] < D)
{
printf("Insufficient Density\n");
exit(0);
}
}
}
}
std::vector<int> t = longest_trip(N, D);
int l = t.size();
printf("%d\n", l);
for (int i = 0; i < l; ++i)
{
printf(i == 0 ? "%d" : " %d", t[i]);
}
printf("\n");
printf("%d\n", call_counter);
maximumCalls = std::max(maximumCalls, call_counter);
call_counter = 0;
}
printf("%d\n", maximumCalls);
return 0;
}
#endif
Compilation message
longesttrip.cpp: In function 'void makePath(std::vector<int>&, std::vector<int>&)':
longesttrip.cpp:185:13: warning: label 'out' defined but not used [-Wunused-label]
185 | out:
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
191 ms |
848 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
336 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
336 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
336 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
