Submission #961901

#	Time	Username	Problem	Language	Result	Execution time	Memory
961901		kilkuwu	Fun Tour (APIO20_fun)	C++17	100 / 100	185 ms	22268 KiB

fun

#include "fun.h"

#include <bits/stdc++.h>

#ifdef LOCAL
#define clog std::cerr
#else 
#define clog if (0) std::cerr
#endif

std::vector<int> createFunTour(int N, int Q) {
  std::vector<std::pair<int, int>> subtree_size(N);
  subtree_size[0] = {N, 0};
  for (int i = 1; i < N; i++) {
    subtree_size[i] = {attractionsBehind(0, i), i};
  }

  std::sort(subtree_size.begin(), subtree_size.end());

  int centroid = -1;
  for (centroid = 0; centroid < N; centroid++) {
    if (subtree_size[centroid].first >= (N + 1) / 2) {
      centroid = subtree_size[centroid].second;
      break;
    }
  }
  
  assert(centroid != -1);

  std::vector<int> adj;
  std::vector<int> d(N);
  for (int i = 0; i < N; i++) {
    if (i == centroid) {
      d[i] = 0;
    } else {
      d[i] = hoursRequired(centroid, i);
    }

    if (d[i] == 1) {
      adj.push_back(i); 
    }
  }

  std::vector<int> g(N, -1);
  std::vector<std::vector<int>> f(3);

  for (int i = 0; i < N; i++) {
    if (i == centroid) continue;

    g[i] = 0;
    while (g[i] + 1 < (int) adj.size() && hoursRequired(adj[g[i]], i) > d[i]) {
      g[i]++;
    }
    f[g[i]].push_back(i);
  }

  std::vector<int> p = {0, 1, 2};

  std::vector<int> tour;

  auto shortest = [&](int i, int j) {
    return d[i] < d[j];
  };

  for (int i = 0; i < 3; i++) {
    std::sort(f[i].begin(), f[i].end(), shortest);
  }

  auto bigger_size = [&](int i, int j) {
    return f[i].size() > f[j].size();
  };

  auto farthest = [&](int i, int j) {
    return d[f[i].back()] > d[f[j].back()];
  };

  std::sort(p.begin(), p.end(), bigger_size);

  int last = -1;
  while (f[p[0]].size() < f[p[1]].size() + f[p[2]].size()) {
    std::sort(p.begin(), p.end(), farthest);
    int now = p[p[0] == last];
    tour.push_back(f[now].back());
    f[now].pop_back();
    last = now;
    std::sort(p.begin(), p.end(), bigger_size);
  }

  f[p[1]].insert(f[p[1]].end(), f[p[2]].begin(), f[p[2]].end());
  std::sort(f[p[1]].begin(), f[p[1]].end(), shortest);

  int from = 0;
  if (tour.size() && d[tour.back()] < d[f[p[1]].back()]) {
    from = 1;
  }

  while (f[p[from]].size()) {
    tour.push_back(f[p[from]].back());
    f[p[from]].pop_back();
    from ^= 1;
  }

  tour.push_back(centroid);

  return tour;
}

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