Submission #1006877

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006877		NeroZein	Longest Trip (IOI23_longesttrip)	C++17	40 / 100	903 ms	1636 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>

using namespace std; 

const int MAXN = 300;

vector<int> g[MAXN];
int pr[MAXN], dep[MAXN];

void dfs(int v) {
  for (int u : g[v]) {
    if (dep[u] != -1) continue; 
    dep[u] = dep[v] + 1; 
    pr[u] = v; 
    dfs(u); 
  }
}

vector<int> longest_trip(int N, int D) {
  for (int i = 0; i < N; ++i) {
    for (int j = i + 1; j < N; ++j) {
      if (are_connected({i}, {j})) {
        g[i].push_back(j); 
        g[j].push_back(i); 
      }
    }
  }
  vector<int> ord(N);
  int ans = 0;
  for (int i = 0; i < N; ++i) {
    fill(dep, dep + N, -1);
    dep[i] = 0; 
    dfs(i);
    for (int j = 0; j < N; ++j) {
      if (dep[j] > ans) {
        ord.clear();
        ans = dep[j];
        int u = j; 
        while (true) {
          ord.push_back(u);
          if (u == i) break;
          u = pr[u];
        }
      }
    }
  }
  fill(g, g + N, vector<int>());
  return {ord};
}

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