#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[256];
int child[256];
bool vis[256];
int dp[256];
int dfs(int x){
if(dp[x]!=-1) return dp[x];
dp[x]=0;
vis[x]=1;
for(auto u:adj[x]){
if(vis[u]) continue;
if(dp[x]<dfs(u)+1){
dp[x]=dp[u]+1;
child[x]=u;
}
}
return dp[x];
}
std::vector<int> longest_trip(int N, int D)
{
for (int i = 0; i < N; ++i)
{
adj[i].clear();
}
for (int i = 0; i < N; ++i)
{
for (int j = i+1; j < N; ++j)
{
if(are_connected({i},{j})){
adj[i].push_back(j);
adj[j].push_back(i);
}
}
}
int sum=0;
vector<int> ans;
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
vis[j]=0;
child[j]=j;
dp[j]=-1;
}
if(sum<dfs(i)){
sum=dfs(i);
ans.clear();
int cur=i;
while(child[cur]!=cur){
ans.push_back(cur);
cur=child[cur];
}
ans.push_back(cur);
}
}
return ans;
}
# | 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... |