# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1069771 | UmairAhmadMirza | Longest Trip (IOI23_longesttrip) | C++17 | 962 ms | 744 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 <bits/stdc++.h>
using namespace std;
bool are_connected(vector<int> A, vector<int> B);
int const MAXN=260;
bool con[MAXN][MAXN];
vector<int> path,longest;
bool vis[MAXN];
int nn;
void dfs(int node){
path.push_back(node);
if(path.size()>longest.size())
longest=path;
vis[node]=1;
for(int i=0;i<nn;i++)
if(vis[i]==0 && con[node][i])
dfs(i);
path.pop_back();
}
vector<int> longest_trip(int n, int D){
longest.clear();
nn=n;
vector<int> a,b;
for(int i=0;i<n;i++){
a.push_back(i);
for(int j=i+1;j<n;j++){
b.push_back(j);
con[i][j]=are_connected(a,b);
con[j][i]=con[i][j];
b.pop_back();
}
a.pop_back();
}
if(D>1){
path.clear();
for (int i = 0; i < n; ++i)
path.push_back(i);
bool bl=0;
for(int i=0;i<n-1;i++)
if(con[path[i]][path[i+1]]==0){
if(i==n-2)
rotate(path.rbegin(), path.rbegin() + 1, path.rend());
else
swap(path[i+1],path[i+2]);
}
return path;
}
for (int i = 0; i < n; ++i)
{
path.clear();
for(int j=0;j<n;j++)
vis[j]=0;
dfs(i);
}
return longest;
}
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... |