#include "longesttrip.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
//#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;
int c[257][257];
int sor(int a,int b) {
if (c[a][b] != -1) return c[a][b];
if (c[b][a] != -1) return c[b][a];
if (a == b) return 0;
return c[a][b] = are_connected({a},{b});
}
int sor(vi v1,vi v2) {
if (v1.empty() || v2.empty()) return 0;
return are_connected(v1,v2);
}
std::vector<int> longest_trip(int N, int D)
{
memset(c,-1,sizeof c);
vi perm(N);
iota(all(perm),0ll);
shuffle(all(perm),mt19937());
vi path,path2;
path.push_back(perm[0]);
for (int i=1;i<N;i++) {
if (sor(path.back(),perm[i])) {
path.push_back(perm[i]);
}else {
if (path2.empty() || sor(path2.back(),perm[i])) {
path2.push_back(perm[i]);
}else {
for (auto it : path2) path.push_back(it);
path2.clear();
path2.push_back(perm[i]);
}
}
}
assert(!path.empty());
if (!path2.empty() && sor(path,path2)) {
vi uc1 = {path.front(),path.back()};
vi uc2 = {path2.front(),path2.back()};
if (sor(uc1[0],uc2[0])) {
reverse(all(path));
for (auto it : path2) path.push_back(it);
return path;
}
else if (big(uc2) > 1 && sor(uc1[0],uc2[1])) {
reverse(all(path));
reverse(all(path2));
for (auto it : path2) path.push_back(it);
return path;
}
else if (big(uc1) > 1 && sor(uc1[1],uc2[0])) {
for (auto it : path2) path.push_back(it);
return path;
}
else {
reverse(all(path2));
for (auto it : path2) path.push_back(it);
return path;
}
assert(0);
//ikisi de cycle (bs)
int l = 1;
int r = path.size();
while (l<=r) {
int m = (l+r) >> 1;
vi v;
for (int j = 0;j<m;j++) v.push_back(path[j]);
if (sor(v,path2)) r = m-1;
else l = m+1;
}
int p1 = l;
assert(sor({path[p1-1]},path2));
l = 1;
r = path2.size();
while (l<=r) {
int m = (l+r) >> 1;
vi v;
for (int j = 0;j<m;j++) v.push_back(path2[j]);
if (sor(v,vi{path[p1-1]})) r = m-1;
else l = m+1;
}
int p2 = l;
vi ans;
for (int j = p1;j<path.size();j++) ans.push_back(path[j]);
for (int j = 0;j<p1;j++) ans.push_back(path[j]);
for (int j = p2-1;j<path2.size();j++) ans.push_back(path2[j]);
for (int j = 0;j<p2-1;j++) ans.push_back(path2[j]);
return ans;
}
else {
if (path.size() >= path2.size()) return path;
return path2;
}
}
# | 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... |