Submission #802925

#	Time	Username	Problem	Language	Result	Execution time	Memory
802925		radaiosm7	Fun Tour (APIO20_fun)	C++11	26 / 100	25 ms	472 KiB

fun

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

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;
}

int bfs(int s) {
  Q.push(s);
  int v = s;
  d[s] = 0;
  fill(visited, visited+n, false);
  visited[s] = true;

  while (!Q.empty()) {
    int x = Q.front();
    Q.pop();
    
    if (!checked[x] && d[x] > d[v]) v = x;
    
    for (auto y : adj[x]) {
      if (visited[y]) continue;
      visited[y] = true;
      Q.push(y);
      d[y] = d[x]+1;
    }
  }

  return v;
}

vector<int> createFunTour(int N, int q) {
  n = N;

  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(bfs(0));
  checked[ans[0]] = true;

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

  return ans;
}

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