Submission #802905

#	Time	Username	Problem	Language	Result	Execution time	Memory
802905		radaiosm7	Fun Tour (APIO20_fun)	C++11	10 / 100	2080 ms	380 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
vector<int> ans;
int i, j;
vector<int> adj[505];
bool checked[505];

pair<int, int> findFar(int x, int p=-1, int dist=0) {
  pair<int, int> mxDist = make_pair(0, -1);
  if (!checked[x]) mxDist = make_pair(dist, x);

  for (auto y : adj[x]) {
    if (y == p) continue;
    mxDist = max(mxDist, findFar(y, x, dist+1));
  }

  return mxDist;
}

vector<int> createFunTour(int n, int q) {
  for (i=0; i < n; ++i) {
    for (j=0; j < n; ++j) {
      if (i == j) continue;
      if (hoursRequired(i,j) == 1) {
        adj[i].push_back(j);
        adj[j].push_back(i);
      }
    }
  }


  fill(checked, checked+n, false);
  ans.push_back(findFar(0).Y);
  checked[ans[0]] = true;

  for (i=1; i < n; ++i) {
    ans.push_back(findFar(ans[i-1]).Y);
    checked[ans[i]] = true;
  }

  return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 16
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34