#include "longesttrip.h"
#include "bits/stdc++.h"
using g_t = std::vector<std::vector<int>>;
std::vector<int> longest_trip(int N, int D) {
using namespace std;
vector<int> se(N);
std::iota(se.begin(), se.end(), 0);
std::random_device rd;
std::mt19937 g(rd());
shuffle(se.begin(), se.end(), g);
int st = se.back();
se.pop_back();
int oSt = se.back();
se.pop_back();
int loopSt = st, loopEn = st, oEnSt = oSt, oEnEn = oSt, oNC = -1;
g_t gr(N);
while (!se.empty() || oNC != -1) {
if (oNC == -1) {
oNC = se.back();
se.pop_back();
} else {
if (are_connected({oEnEn}, {oNC})) {
gr[oEnEn].push_back(oNC);
gr[oNC].push_back(oEnEn);
oEnEn = oNC;
oNC = -1;
} else {
if (are_connected({oNC}, {loopEn})) {
gr[loopEn].push_back(oNC);
gr[oNC].push_back(loopEn);
loopEn = oNC;
oNC = -1;
} else {
gr[loopEn].push_back(oEnEn);
gr[oEnEn].push_back(loopEn);
loopEn = oEnSt;
oEnSt = oNC;
oEnEn = oNC;
oNC = -1;
}
}
}
}
if (!are_connected({loopSt}, {loopEn})) {
if (are_connected({loopEn}, {oEnEn})) {
gr[loopEn].push_back(oEnEn);
gr[oEnEn].push_back(loopEn);
loopEn = oEnSt;
} else {
gr[loopSt].push_back(oEnEn);
gr[oEnEn].push_back(loopSt);
loopSt = oEnSt;
}
} else if (!are_connected({oEnEn}, {oEnSt})) {
if (are_connected({loopEn}, {oEnEn})) {
gr[loopEn].push_back(oEnEn);
gr[oEnEn].push_back(loopEn);
loopEn = oEnSt;
} else {
gr[loopEn].push_back(oEnSt);
gr[oEnSt].push_back(loopEn);
loopEn = oEnEn;
}
} else {
assert(false);
int act = loopSt;
vector<int> reLo{{act}};
if (!gr[act].empty()) {
act = gr[act][0];
while (true) {
int ne = gr[act][0];
if (ne == reLo.back() && gr[act].size() > 1) ne = gr[act][1];
reLo.push_back(act);
if (gr[act].size() == 1) {
break;
}
act = ne;
}
}
act = oEnSt;
vector<int> reoEn{{act}};
if (!gr[act].empty()) {
act = gr[act][0];
while (true) {
int ne = gr[act][0];
if (ne == reoEn.back() && gr[act].size() > 1) ne = gr[act][1];
reoEn.push_back(act);
if (gr[act].size() == 1) {
break;
}
act = ne;
}
}
if (!are_connected(reLo, reoEn)) {
if (reLo.size() > reoEn.size()) return reLo;
return reoEn;
}
int l = 0, r = reoEn.size();
while (l + 1 < r) {
int m = (l + r) / 2;
vector<int> relv;
for (int i = l; i < m; ++i) {
relv.push_back(reoEn[i]);
}
if (are_connected(relv, reLo)) r = m;
else l = m;
}
int ll = 0, rr = reLo.size();
while (ll + 1 < rr) {
int m = (ll + rr) / 2;
vector<int> relv;
for (int i = ll; i < m; ++i) {
relv.push_back(reLo[i]);
}
if (are_connected({reoEn[l]}, relv)) rr = m;
else ll = m;
}
vector<int> res;
for (int i = 0; i < reLo.size(); ++i) {
res.push_back(reLo[(ll + 1 + i) % reLo.size()]);
}
for (int i = 0; i < reoEn.size(); ++i) {
res.push_back(reoEn[(l + i) % reoEn.size()]);
}
return res;
}
int act = loopSt;
vector<int> res{{act}};
if (!gr[act].empty()) {
act = gr[act][0];
while (true) {
int ne = gr[act][0];
if (ne == res.back() && gr[act].size() > 1) ne = gr[act][1];
res.push_back(act);
if (gr[act].size() == 1) {
break;
}
act = ne;
}
}
return res;
}
Compilation message
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:121:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for (int i = 0; i < reLo.size(); ++i) {
| ~~^~~~~~~~~~~~~
longesttrip.cpp:124:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | for (int i = 0; i < reoEn.size(); ++i) {
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
non-disjoint arrays |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
non-disjoint arrays |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
non-disjoint arrays |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
non-disjoint arrays |
| 2 |
Halted |
0 ms |
0 KB |
- |
