This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 256;
int n , d;
bool in_path[N];
vector <int> maximal()
{
for(int i = 0 ; i < n ; i++)
in_path[i] = false;
vector <int> vec;
vec.push_back(0);
in_path[0] = true;
while(vec.size() < n)
{
vector <int> A; A.push_back(vec.back());
vector <int> B;
for(int i = 0 ; i < n ; i++) if(!in_path[i])
B.push_back(i);
if(!are_connected(A , B))
break;
int low = 0 , high = B.size();
while(high - low > 1)
{
int mid = (low + high) >> 1;
vector <int> tmp;
for(int i = low ; i < mid ; i++)
tmp.push_back(B[i]);
if(are_connected(A , tmp))
high = mid;
else
low = mid;
}
in_path[B[low]] = true;
vec.push_back(B[low]);
}
reverse(vec.begin() , vec.end());
while(vec.size() < n)
{
vector <int> A; A.push_back(vec.back());
vector <int> B;
for(int i = 0 ; i < n ; i++) if(!in_path[i])
B.push_back(i);
if(!are_connected(A , B))
break;
int low = 0 , high = B.size();
while(high - low > 1)
{
int mid = (low + high) >> 1;
vector <int> tmp;
for(int i = low ; i < mid ; i++)
tmp.push_back(B[i]);
if(are_connected(A , tmp))
high = mid;
else
low = mid;
}
in_path[B[low]] = true;
vec.push_back(B[low]);
}
return vec;
}
vector<int> longest_trip(int nn, int dd)
{
n = nn;
d = dd;
vector <int> vec = maximal();
vector <int> comp;
for(int i = 0 ; i < n ; i++) if(!in_path[i])
comp.push_back(i);
if(comp.empty())
return vec;
if(!are_connected(vec , comp))
{
if(vec.size() > comp.size())
return vec;
else
return comp;
}
int low = 0 , high = vec.size();
while(high - low > 1)
{
int mid = (low + high) >> 1;
vector <int> tmp;
for(int i = low ; i < mid ; i++)
tmp.push_back(vec[i]);
if(are_connected(tmp , comp))
high = mid;
else
low = mid;
}
vector <int> res;
for(int i = low + 1 ; i < vec.size() ; i++)
res.push_back(vec[i]);
for(int i = 0 ; i <= low ; i++)
res.push_back(vec[i]);
low = 0; high = comp.size();
vector <int> A; A.push_back(res.back());
while(high - low > 1)
{
int mid = (low + high) >> 1;
vector <int> B;
for(int i = low ; i < mid ; i++)
B.push_back(comp[i]);
if(are_connected(A , B))
high = mid;
else
low = mid;
}
res.push_back(comp[low]);
for(int i = 0 ; i < comp.size() ; i++) if(i != low)
res.push_back(comp[i]);
return res;
}
Compilation message (stderr)
longesttrip.cpp: In function 'std::vector<int> maximal()':
longesttrip.cpp:17:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
17 | while(vec.size() < n)
| ~~~~~~~~~~~^~~
longesttrip.cpp:41:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
41 | while(vec.size() < n)
| ~~~~~~~~~~~^~~
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:97:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int i = low + 1 ; i < vec.size() ; i++)
| ~~^~~~~~~~~~~~
longesttrip.cpp:115:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for(int i = 0 ; i < comp.size() ; i++) if(i != low)
| ~~^~~~~~~~~~~~~
# | 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... |