# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1063942 | parsadox2 | Longest Trip (IOI23_longesttrip) | C++17 | 70 ms | 708 KiB |
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();
if(vec.size() > n / 2)
return vec;
vector <int> comp;
for(int i = 0 ; i < n ; i++) if(!in_path[i])
comp.push_back(i);
return comp;
return vec;
}
Compilation message (stderr)
# | 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... |