Submission #839930

#	Time	Username	Problem	Language	Result	Execution time	Memory
839930		pere_gil	Longest Trip (IOI23_longesttrip)	C++17	15 / 100	962 ms	756 KiB

longesttrip

#include "longesttrip.h"
#include "bits/stdc++.h"
using namespace std;

#define vi vector<int>
#define ii pair<int,int>

const int mxn=257;
vector<int> adj[mxn];

ii dfs(int u, vector<bool> &vis, vi &res, bool sw){
  vis[u]=true;
  ii best={0,u};
  int nxt=u;
  for(int v: adj[u]){
    if(vis[v]) continue;
    ii act=dfs(v,vis,res,sw);
    if(act.first+1>best.first) best={act.first+1,act.second},nxt=v;
  }
  
  if(sw && nxt!=u) res.push_back(nxt);
  
  return best;
}

vi 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);

  vector<bool> first(n,false),second(n,false);
  vector<int> res;
  for(int i=0;i<n;i++){
    if(first[i]) continue;
    vi act;
    int st=dfs(i,first,act,false).second;
    dfs(st,second,act,true);
    act.push_back(st);

    if(act.size()>res.size()) res=act;
  }
  
  return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 60