Submission #741412

#	Time	Username	Problem	Language	Result	Execution time	Memory
741412		vjudge1	Fun Tour (APIO20_fun)	C++17	26 / 100	50 ms	35732 KiB

fun

///////////////////////////////////////////

#include "fun.h"

#include <vector>
#include <bits/stdc++.h>

using namespace std;

const int N2 = 1000;
int d[N2][N2];
vector <int> a[N2];
bool vis[N2];

void dfs(vector <int> &d, int u, int par = -1){
  for(int i : a[u]){
    if (i == par || vis[i]) continue;

    d[i] = d[u] + 1;
    dfs(d, i, u);
  }
}

std::vector<int> createFunTour(int N, int Q) {
  for(int i = 0; i < N; ++i){
    for(int j = i + 1; j < N; ++j){
      d[i][j] = d[j][i] = hoursRequired(i, j);
      if (hoursRequired(i, j) == 1){
        a[i].push_back(j);
        a[j].push_back(i);
      }
    }
  }

  vector <int> d(N, 0);
  dfs(d, 1);

  pair<int, int> ma = {-1, -1};
  for(int i = 0; i < N; ++i){
    ma = max(ma, {d[i], i});
  }

  vector <int> ans;

  int u = ma.second;
  ans.push_back(u);
  vis[u] = true;

  while ((int)ans.size() < N){
    d[u] = 0; dfs(d, u);

    pair<int, int> ma = {-1, -1};
    for(int i = 0; i < N; ++i){
      if (vis[i]) continue;
      ma = max(ma, {d[i], i});
    }

    u = ma.second;
    ans.push_back(u);
    vis[u] = true;
  }

  return ans;
}

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