#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define ll long long
#define ff first
#define ss second
#define vi vector<int>
const int N = 200005;
std::vector<int> longest_trip(int n, int D)
{
if(D == 3){
vector<int> v;
for(int i = 0; i < n; ++i) v.pb(i);
return v;
}
if(D == 2){
deque<int> v;
v.pb(0);
int o = -1;
for(int i = 1; i < n; ++i){
bool x = are_connected(vi{0}, vi{i});
if(x){
o = i;
v.pb(i);
break;
}
}
if(o == -1){
vi res;
for(int i = 1; i < n; ++i){
res.pb(i);
}
return res;
}
for(int i = 1; i < n; ++i){
if(o == i) continue;
bool x = are_connected(vi{v[0]}, vi{i});
if(x){
v.push_front(i);
}else v.pb(i);
}
vector<int> res(all(v));
return res;
}
vector<vector<int>> g(n);
vector<vector<bool>> is(n, vector<bool>(n));
for(int i = 0; i < n; ++i){
for(int j = i + 1; j < n; ++j){
bool ok = are_connected(vi{i}, vi{j});
if(ok){
is[i][j] = is[j][i] = 1;
g[i].pb(j);
g[j].pb(i);
}
}
}
vector<vector<int>> S;
for(int i = 0; i < n; ++i){
if(g[i].empty()){
vi res;
for(int j = 0; j < n; ++j){
if(j != i) res.pb(j);
}
return res;
}
bool okk = 0;
for(auto &s: S){
bool ok = 1;
for(int x: s){
if(is[x][i] == 0) ok = 0;
}
if(ok == 1){
s.pb(i);
okk = 1;
break;
}
}
if(okk == 0){
S.pb(vi{i});
}
}
if(S.size() == 2){
for(int &x: S[0]){
for(int &y: S[1]){
if(is[x][y]){
swap(x, S[0].back());
swap(y, S[1][0]);
vi res;
for(int f: S[0]) res.pb(f);
for(int f: S[1]) res.pb(f);
return res;
}
}
}
if(S[0].size() > S[1].size()) return S[0];
return S[1];
}
vi res;
int o = 0;
for(int i = 0; i < S.size(); ++i){
if(S[i].size() == 1){
if(o == 0){
S[0].swap(S[i]);
++o;
}else if(o == 1){
S.back().swap(S[i]);
o += 2;
break;
}
}
}
if(o == 1){
bool ok = 0;
for(int i = 1; i < S.size(); ++i){
for(int x: S[i]){
if(is[x][S[0][0]]){
ok = 1;
break;
}
}
if(ok){
S[1].swap(S[i]);
break;
}
}
}else if(o == 2){
for(int i = 0; i + 1 < S.size(); ++i){
bool ok = 0;
for(int x: S[i]){
if(is[x][S.back()[0]]){
ok = 1;
break;
}
}
if(ok){
S[int(S.size()) - 2].swap(S[i]);
break;
}
}
}else if(o == 3 && S.size() > 3){
vector<bool> b(S.size());
vector<bool> b2(S.size());
for(int i = 1; i < S.size(); ++i){
bool ok = 0;
for(int x: S[i]){
if(is[x][S[0][0]]){
ok = 1;
break;
}
}
if(ok){
b[i] = 1;
}
}
for(int i = 0; i + 1 < S.size(); ++i){
bool ok = 0;
for(int x: S[i]){
if(is[x][S.back()[0]]){
ok = 1;
break;
}
}
if(ok){
b2[i] = 1;
break;
}
}
bool okk = 0;
for(int i = 0; i < S.size(); ++i){
for(int j = 0; j < S.size(); ++j){
if(i == j) continue;
if(b[i] && b2[j]){
S[i].swap(S[1]);
if(j == 1){
S[int(S.size()) - 2].swap(S[i]);
}else{
S[int(S.size()) - 2].swap(S[j]);
}
okk = 1;
break;
}
}
if(okk) break;
}
if(!okk) assert(false);
}
for(int i = 0; i < S.size(); ++i){
if(i + 1 < S.size()){
for(int x: S[i]) res.pb(x);
}else{
bool ok = 0;
for(int j = (int(S[i].size() == 1 ? 0 : 1)); j < S[i].size(); ++j){
for(int l = 0; l < S[i + 1].size(); ++l){
if(is[S[i][j]][S[i + 1][l]]){
swap(S[i][j], S[i].back());
swap(S[i + 1][l], S[i + 1][0]);
ok = 1;
break;
}
}
if(ok) break;
}
for(int x: S[i]) res.pb(x);
}
}
return res;
}
Compilation message
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:103:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for(int i = 0; i < S.size(); ++i){
| ~~^~~~~~~~~~
longesttrip.cpp:117:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
117 | for(int i = 1; i < S.size(); ++i){
| ~~^~~~~~~~~~
longesttrip.cpp:130:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | for(int i = 0; i + 1 < S.size(); ++i){
| ~~~~~~^~~~~~~~~~
longesttrip.cpp:146:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | for(int i = 1; i < S.size(); ++i){
| ~~^~~~~~~~~~
longesttrip.cpp:158:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
158 | for(int i = 0; i + 1 < S.size(); ++i){
| ~~~~~~^~~~~~~~~~
longesttrip.cpp:172:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
172 | for(int i = 0; i < S.size(); ++i){
| ~~^~~~~~~~~~
longesttrip.cpp:173:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
173 | for(int j = 0; j < S.size(); ++j){
| ~~^~~~~~~~~~
longesttrip.cpp:190:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
190 | for(int i = 0; i < S.size(); ++i){
| ~~^~~~~~~~~~
longesttrip.cpp:191:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
191 | if(i + 1 < S.size()){
| ~~~~~~^~~~~~~~~~
longesttrip.cpp:195:54: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
195 | for(int j = (int(S[i].size() == 1 ? 0 : 1)); j < S[i].size(); ++j){
| ~~^~~~~~~~~~~~~
longesttrip.cpp:196:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
196 | for(int l = 0; l < S[i + 1].size(); ++l){
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
196 ms |
1540 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
1 ms |
440 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
344 KB |
Output is correct |
| 2 |
Correct |
5 ms |
344 KB |
Output is correct |
| 3 |
Correct |
5 ms |
344 KB |
Output is correct |
| 4 |
Correct |
6 ms |
344 KB |
Output is correct |
| 5 |
Correct |
7 ms |
344 KB |
Output is correct |
| 6 |
Correct |
6 ms |
344 KB |
Output is correct |
| 7 |
Correct |
5 ms |
344 KB |
Output is correct |
| 8 |
Correct |
5 ms |
344 KB |
Output is correct |
| 9 |
Correct |
7 ms |
344 KB |
Output is correct |
| 10 |
Correct |
5 ms |
436 KB |
Output is correct |
| 11 |
Correct |
7 ms |
344 KB |
Output is correct |
| 12 |
Correct |
5 ms |
432 KB |
Output is correct |
| 13 |
Correct |
7 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
