Submission #982413

#	Time	Username	Problem	Language	Result	Execution time	Memory
982413		Marcus	Fun Tour (APIO20_fun)	C++17	26 / 100	257 ms	524288 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
#include <vector>
int n, q;
vector<vector<int>> adj(1e5);
 
std::vector<int> createFunTour(int N, int Q) {
  n=N; q=Q;
  vector<vector<int>> dist(n, vector<int>(n, -1));
  for (int i=0; i<n; i++)
  {
    for (int j=0; j<n; j++)
    {
        dist[i][j] = hoursRequired(i, j);
    }
  }
  vector<int> answer;
  pair<int, int> maxzero = {-1, -1};
  for (int i=0; i<n; i++)
  {
    if (dist[0][i] > maxzero.first) {maxzero = {dist[0][i], i};}
  }
  vector<int> visited(n);
  answer.push_back(maxzero.second);
  visited[answer.back()] = true;
  while ((int)answer.size() < n)
  {
    pair<int, int> maximal = {-1, -1};
    for (int i=0; i<n; i++)
    {
        if (visited[i]) continue;
        if (dist[answer.back()][i] > maximal.first) {maximal = {dist[answer.back()][i], i};}
    }
    answer.push_back(maximal.second);
    visited[answer.back()] = true;
  }

  return answer;
}

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