#include <bits/stdc++.h>
// #include "longesttrip.h"
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
// #ifdef LOCAL
// vector<vector<int>> G_secret;
// int n;
// bool are_connected(vector<int> a, vector<int> b) {
// for (int i : a) {
// for (int j : b) {
// if (G_secret[i][j])
// return true;
// }
// }
// return false;
// }
// #endif
#ifdef LOCAL
// #include "longesttrip.h"
#include <cassert>
#include <cstdio>
#include <string>
#include <vector>
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;
}
#endif
struct dsu {
vector<int> p;
dsu(int n) {
p.resize(n);
iota(all(p), 0);
}
int get(int a) {
if (p[a] == a)
return a;
return p[a] = get(p[a]);
}
void merge(int a, int b) {
a = get(a), b = get(b);
p[a] = b;
}
};
vector<int> get_comp(int n, int v, dsu &d) {
vector<int> comp;
for (int i = 0; i < n; ++i) {
if (d.get(i) == v) {
comp.push_back(i);
}
}
return comp;
}
void add_comp(vector<int> &ans, vector<int> &comp, pair<int, int> end) {
ans.push_back(end.first);
for (int j : comp) {
if (j != end.first && j != end.second) {
ans.push_back(j);
}
}
if (end.first != end.second) {
ans.push_back(end.second);
}
}
vector<int> longest_trip(int n, int D) { // Случай, когда отдельная вершинка - 0
dsu d(n);
vector<vector<int>> path;
vector<pair<int, int>> ends;
ends.push_back({0, 0});
path.push_back({0});
vector<int> ost(n - 1);
iota(all(ost), 1);
while (true) {
int ind_comp = ost[0];
bool find = false;
bool was_merge = false;
for (int i = 0; i < (int) ost.size(); ++i) {
if (are_connected({ends.back().second}, get_comp(n, ost[i], d))) {
path.push_back(get_comp(n, ost[i], d));
int last_end = ends.back().second;
ends.emplace_back();
for (int i : path.back()) { // поиск вершины.
if (are_connected({last_end}, {i})) {
ends.back().first = i;
}
}
if (path.back().size() == 1) {
ends.back().second = ends.back().first;
} else {
if (ends.back().first != path.back()[0]) {
ends.back().second = path.back()[0];
} else {
ends.back().second = path.back().back();
}
}
swap(ost[i], ost.back());
ost.pop_back();
find = true;
break;
} else {
was_merge = true;
d.merge(ost[i], ind_comp);
swap(ost[i], ost.back());
ost.pop_back();
--i;
}
}
if (was_merge)
ost.push_back(ind_comp);
if (!ost.size()) {
vector<int> ans;
for (int i = 0; i < (int) path.size(); ++i) {
add_comp(ans, path[i], ends[i]);
}
// cout << "MEOW1\n";
return ans;
}
if (!find) {
vector<int> last_comp = get_comp(n, ost[0], d);
for (int i = 0; i < (int) path.size(); ++i) {
if (are_connected({last_comp[0]}, {ends[i].first})) {
vector<int> ans;
for (int j : last_comp) {
if (j != last_comp[0]) {
ans.push_back(j);
}
}
ans.push_back(last_comp[0]);
for (int j = i; j < (int) path.size(); ++j) {
add_comp(ans, path[j], ends[j]);
}
for (int j = 0; j < i; ++j) {
add_comp(ans, path[j], ends[j]);
}
// cout << "MEOW2\n";
return ans;
}
}
vector<int> ans;
if (last_comp.size() > n - last_comp.size()) {
for (int i : last_comp)
ans.push_back(i);
} else {
for (auto i : path) {
for (int j : i)
ans.push_back(j);
}
}
return ans;
}
}
assert(0);
return {-1};
}
#ifdef LOCAL
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 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:186:17: error: 'are_connected' was not declared in this scope
186 | if (are_connected({ends.back().second}, get_comp(n, ost[i], d))) {
| ^~~~~~~~~~~~~
longesttrip.cpp:229:21: error: 'are_connected' was not declared in this scope
229 | if (are_connected({last_comp[0]}, {ends[i].first})) {
| ^~~~~~~~~~~~~
