#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
/*
OBSERVE:
path meargen
hinten und vorne dazu
* - * *
* - *
*/
std::vector<int> longest_trip(int N, int D){
// vorraussetzung path[0].end nicht mit path[1].end verbunden
vector<int> path[2];
path[0].push_back(0);
for(int i=1; i<N; i++){
if(are_connected({*path[0].rbegin()}, {i})){
path[0].push_back(i);
if(path[1].size() and are_connected({path[0][path[0].size()-1]}, {path[1][path[1].size()-1]})){
reverse(path[1].begin(), path[1].end());
path[0].insert(path[0].end(), path[1].begin(), path[1].end());
path[1].clear();
}
}else{
path[1].push_back(i);
}
}
if(path[1].empty() or not are_connected(path[0], path[1])){
if(path[0].size() > path[1].size())
return path[0];
return path[1];
}
if(are_connected({path[0][0]}, {path[1][0]})){
reverse(path[0].begin(), path[0].end());
path[0].insert(path[0].end(), path[1].begin(), path[1].end());
return path[0];
}
if(are_connected({path[0][0]}, {path[1][path[1].size()-1]})){
path[1].insert(path[1].end(), path[0].begin(), path[0].end());
return path[1];
}
if(are_connected({path[0][path[0].size()-1]}, {path[1][0]})){
path[0].insert(path[0].end(), path[1].begin(), path[1].end());
return path[0];
}
// jetzt wissen wir das path[0].begin - path[0].end
// jetzt wissen wir das path[1].begin - path[1].end
// und die pfade sind nicht disjoint
// eine node in path[0] finden die mit path[1] verbunden ist
for(int i=0; i<path[0].size(); i++){
if(are_connected({path[0][i]}, path[1])){
for(int j=0; i<path[1].size(); j++){
if(are_connected({path[0][i]}, {path[1][j]})){
vector<int> ans;
reverse(path[0].begin() + i + 1, path[0].end());
ans.insert(ans.end(), path[0].begin() + i + 1, path[0].end());
ans.insert(ans.end(), path[0].begin(), path[0].begin() + i + 1);
ans.insert(ans.end(), path[1].begin() + j, path[1].end());
ans.insert(ans.end(), path[1].begin(), path[1].begin() + j);
return ans;
}
}
}
}
assert(false);
}
Compilation message
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:68:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(int i=0; i<path[0].size(); i++){
| ~^~~~~~~~~~~~~~~
longesttrip.cpp:70:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for(int j=0; i<path[1].size(); j++){
| ~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
344 KB |
Output is correct |
2 |
Correct |
4 ms |
344 KB |
Output is correct |
3 |
Correct |
4 ms |
344 KB |
Output is correct |
4 |
Correct |
4 ms |
340 KB |
Output is correct |
5 |
Correct |
5 ms |
344 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 |
4 ms |
344 KB |
Output is correct |
4 |
Correct |
5 ms |
344 KB |
Output is correct |
5 |
Correct |
5 ms |
344 KB |
Output is correct |
6 |
Correct |
8 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 |
4 ms |
344 KB |
Output is correct |
10 |
Correct |
4 ms |
344 KB |
Output is correct |
11 |
Correct |
4 ms |
344 KB |
Output is correct |
12 |
Correct |
4 ms |
344 KB |
Output is correct |
13 |
Correct |
4 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
344 KB |
Output is correct |
2 |
Correct |
4 ms |
344 KB |
Output is correct |
3 |
Correct |
5 ms |
340 KB |
Output is correct |
4 |
Correct |
4 ms |
344 KB |
Output is correct |
5 |
Correct |
4 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 |
4 ms |
344 KB |
Output is correct |
9 |
Correct |
4 ms |
344 KB |
Output is correct |
10 |
Correct |
4 ms |
344 KB |
Output is correct |
11 |
Correct |
5 ms |
596 KB |
Output is correct |
12 |
Correct |
5 ms |
344 KB |
Output is correct |
13 |
Correct |
4 ms |
440 KB |
Output is correct |
14 |
Correct |
7 ms |
344 KB |
Output is correct |
15 |
Correct |
7 ms |
344 KB |
Output is correct |
16 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
596 KB |
Output is correct |
2 |
Correct |
5 ms |
344 KB |
Output is correct |
3 |
Correct |
4 ms |
344 KB |
Output is correct |
4 |
Correct |
5 ms |
344 KB |
Output is correct |
5 |
Correct |
5 ms |
600 KB |
Output is correct |
6 |
Correct |
7 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 |
5 ms |
340 KB |
Output is correct |
10 |
Correct |
4 ms |
344 KB |
Output is correct |
11 |
Correct |
4 ms |
344 KB |
Output is correct |
12 |
Correct |
5 ms |
600 KB |
Output is correct |
13 |
Correct |
5 ms |
600 KB |
Output is correct |
14 |
Correct |
8 ms |
344 KB |
Output is correct |
15 |
Correct |
8 ms |
344 KB |
Output is correct |
16 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
17 |
Halted |
0 ms |
0 KB |
- |