#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;
deque<int> haha[500];
int n;
void merge(int a, int b) {
for(int i = 0; i < haha[b].size(); i++) {
haha[a].push_front(haha[b][i]);
}
haha[b].clear();
}
int dude(int p1, int p2) {
vector<int> a(0);
vector<int> b(0);
for(int i = 0; i < haha[p2].size(); i++) {
b.push_back(haha[p2][i]);
}
int l = 0,r = haha[p1].size()-1;
while(l < r) {
int m = (l+r)/2;
a.clear();
for(int i = l; i <= m; i++) {
a.push_back(haha[p1][i]);
}
if(are_connected(a,b)) {
r = m;
}
else {
l = m+1;
}
}
return l;
}
std::vector<int> longest_trip(int N, int D)
{
n = N;
for(int i = 0; i < n; i++) {
haha[i].clear();
haha[i].push_back(i);
}
for(int i = 0; i < n-2; i++) {
vector<int> wut(0);
for(int j = 0; j < n; j++) {
if(haha[j].size() > 0) {
wut.push_back(j);
if(wut.size() == 3) {
break;
}
}
}
if(are_connected({haha[wut[0]][0]},{haha[wut[1]][0]})) {
merge(wut[0],wut[1]);
}
else if(are_connected({haha[wut[0]][0]},{haha[wut[2]][0]})) {
merge(wut[0],wut[2]);
}
else {
merge(wut[1],wut[2]);
}
}
int p1 = -1,p2;
for(int i = 0; i < n; i++) {
if(haha[i].size() > 0) {
if(p1 == -1) {
p1 = i;
}
else {
p2 = i;
}
}
}
vector<int> ans(0);
if(are_connected({haha[p1][0]},{haha[p2][0]})) {
for(int i = haha[p1].size()-1; i >= 0; i--) {
ans.push_back(haha[p1][i]);
}
for(int i = 0; i < haha[p2].size(); i++) {
ans.push_back(haha[p2][i]);
}
return ans;
}
if(are_connected({haha[p1][haha[p1].size()-1]},{haha[p2][0]})) {
for(int i = 0; i < haha[p1].size(); i++) {
ans.push_back(haha[p1][i]);
}
for(int i = 0; i < haha[p2].size(); i++) {
ans.push_back(haha[p2][i]);
}
return ans;
}
if(are_connected({haha[p1][0]},{haha[p2][haha[p2].size()-1]})) {
for(int i = haha[p1].size()-1; i >= 0; i--) {
ans.push_back(haha[p1][i]);
}
for(int i = haha[p2].size()-1; i >= 0; i--) {
ans.push_back(haha[p2][i]);
}
return ans;
}
vector<int> a(0);
vector<int> b(0);
for(int i = 0; i < haha[p1].size(); i++) {
a.push_back(haha[p1][i]);
}
for(int i = 0; i < haha[p2].size(); i++) {
b.push_back(haha[p2][i]);
}
if(!are_connected(a,b)) {
if(a.size() > b.size()) {
return a;
}
else {
return b;
}
}
int x1 = dude(p1,p2);
int x2 = dude(p2,p1);
if(are_connected({haha[p1][x1]},{haha[p2][x2]}) == 0) {
cout << 1/0 << endl;
return a;
}
for(int i = x1+1; i < haha[p1].size(); i++) {
ans.push_back(haha[p1][i]);
}
for(int i = 0; i <= x1; i++) {
ans.push_back(haha[p1][i]);
}
for(int i = x2; i < haha[p2].size(); i++) {
ans.push_back(haha[p2][i]);
}
for(int i = 0; i < x2; i++) {
ans.push_back(haha[p2][i]);
}
return ans;
}
Compilation message
longesttrip.cpp: In function 'void merge(int, int)':
longesttrip.cpp:10:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
10 | for(int i = 0; i < haha[b].size(); i++) {
| ~~^~~~~~~~~~~~~~~~
longesttrip.cpp: In function 'int dude(int, int)':
longesttrip.cpp:19:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | for(int i = 0; i < haha[p2].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:83:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for(int i = 0; i < haha[p2].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
longesttrip.cpp:89:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for(int i = 0; i < haha[p1].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
longesttrip.cpp:92:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for(int i = 0; i < haha[p2].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
longesttrip.cpp:108:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(int i = 0; i < haha[p1].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
longesttrip.cpp:111:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for(int i = 0; i < haha[p2].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
longesttrip.cpp:125:18: warning: division by zero [-Wdiv-by-zero]
125 | cout << 1/0 << endl;
| ~^~
longesttrip.cpp:128:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | for(int i = x1+1; i < haha[p1].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
longesttrip.cpp:134:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | for(int i = x2; i < haha[p2].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
2 ms |
600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
600 KB |
Output is correct |
| 2 |
Correct |
10 ms |
600 KB |
Output is correct |
| 3 |
Correct |
9 ms |
600 KB |
Output is correct |
| 4 |
Correct |
5 ms |
600 KB |
Output is correct |
| 5 |
Correct |
8 ms |
600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
600 KB |
Output is correct |
| 2 |
Correct |
5 ms |
600 KB |
Output is correct |
| 3 |
Correct |
8 ms |
600 KB |
Output is correct |
| 4 |
Correct |
5 ms |
600 KB |
Output is correct |
| 5 |
Correct |
5 ms |
600 KB |
Output is correct |
| 6 |
Correct |
6 ms |
600 KB |
Output is correct |
| 7 |
Correct |
6 ms |
600 KB |
Output is correct |
| 8 |
Correct |
5 ms |
600 KB |
Output is correct |
| 9 |
Correct |
7 ms |
852 KB |
Output is correct |
| 10 |
Correct |
8 ms |
600 KB |
Output is correct |
| 11 |
Correct |
6 ms |
600 KB |
Output is correct |
| 12 |
Correct |
6 ms |
600 KB |
Output is correct |
| 13 |
Correct |
6 ms |
600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
600 KB |
Output is correct |
| 2 |
Correct |
5 ms |
600 KB |
Output is correct |
| 3 |
Correct |
5 ms |
600 KB |
Output is correct |
| 4 |
Correct |
5 ms |
600 KB |
Output is correct |
| 5 |
Correct |
6 ms |
600 KB |
Output is correct |
| 6 |
Correct |
6 ms |
600 KB |
Output is correct |
| 7 |
Correct |
4 ms |
600 KB |
Output is correct |
| 8 |
Correct |
7 ms |
600 KB |
Output is correct |
| 9 |
Correct |
5 ms |
600 KB |
Output is correct |
| 10 |
Correct |
6 ms |
600 KB |
Output is correct |
| 11 |
Correct |
5 ms |
768 KB |
Output is correct |
| 12 |
Correct |
6 ms |
600 KB |
Output is correct |
| 13 |
Correct |
6 ms |
600 KB |
Output is correct |
| 14 |
Correct |
11 ms |
600 KB |
Output is correct |
| 15 |
Correct |
11 ms |
600 KB |
Output is correct |
| 16 |
Runtime error |
4 ms |
1112 KB |
Execution killed with signal 8 |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
600 KB |
Output is correct |
| 2 |
Correct |
5 ms |
600 KB |
Output is correct |
| 3 |
Correct |
5 ms |
600 KB |
Output is correct |
| 4 |
Correct |
6 ms |
600 KB |
Output is correct |
| 5 |
Correct |
9 ms |
856 KB |
Output is correct |
| 6 |
Correct |
7 ms |
600 KB |
Output is correct |
| 7 |
Correct |
8 ms |
600 KB |
Output is correct |
| 8 |
Correct |
6 ms |
600 KB |
Output is correct |
| 9 |
Correct |
6 ms |
600 KB |
Output is correct |
| 10 |
Correct |
5 ms |
600 KB |
Output is correct |
| 11 |
Correct |
6 ms |
600 KB |
Output is correct |
| 12 |
Correct |
5 ms |
600 KB |
Output is correct |
| 13 |
Correct |
6 ms |
600 KB |
Output is correct |
| 14 |
Correct |
10 ms |
600 KB |
Output is correct |
| 15 |
Correct |
15 ms |
600 KB |
Output is correct |
| 16 |
Runtime error |
3 ms |
1112 KB |
Execution killed with signal 8 |
| 17 |
Halted |
0 ms |
0 KB |
- |
