Submission #1312051

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312051		maya_s	Fun Tour (APIO20_fun)	C++20	26 / 100	54 ms	15660 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll, ll> pll;

pll farthest(ll n, ll p, ll d, vector<vector<ll>> &g, set<ll> &s){
  pll ans = {d, n};
  for(ll i : g[n]) if(i != p && s.find(i) != s.end()) ans = max(ans, farthest(i, n, d+1, g, s));
  return ans;
}

vector<int> createFunTour(int n, int q){
  vector<vector<ll>> g(n);
  for(ll i = 0; i < n; i++) for(ll j = i+1; j < n; j++) if(hoursRequired(i, j) == 1) g[i].push_back(j), g[j].push_back(i);
  set<ll> s;
  for(ll i = 0; i < n; i++) s.insert(i);
  auto[d, node] = farthest(0, -1, 0, g, s);
  vector<ll> ans;
  do{
    s.erase(node); ans.push_back(node);
    auto[d, x] = farthest(node, -1, 0, g, s);
    node = x;
  }
  while(s.size());
  return ans;
}

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