Submission #961897

#	Time	Username	Problem	Language	Result	Execution time	Memory
961897		kilkuwu	Fun Tour (APIO20_fun)	C++17	21 / 100	92 ms	16328 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);
  int sz = adj.size();
  std::vector<std::vector<int>> f(sz);

  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(sz);
  std::iota(p.begin(), p.end(), 0);
  int last = -1;

  std::vector<int> tour;

  if (sz == 3) {
    while (true) {
      std::sort(p.begin(), p.end(),
                [&](int i, int j) { return f[i].size() > f[j].size(); });

      if (f[p[0]].size() >= f[p[1]].size() + f[p[2]].size()) {
        break;
      }

      // we can still do that
      std::sort(p.begin(), p.end(),
                [&](int i, int j) { return d[f[i].back()] > d[f[j].back()]; });

      int now = p[p[0] == last];
      tour.push_back(f[now].back());
      f[now].pop_back();
      last = now;
    }
    for (int i : f[p[2]]) {
      f[p[1]].emplace_back(i);
    }
    f[p[2]].clear();
    std::sort(f[p[1]].begin(), f[p[1]].end(),
              [&](int i, int j) { return d[i] < d[j]; });
    p.pop_back();
  }

  std::sort(p.begin(), p.end(), [&](int i, int j) {
    return f[i].size() > f[j].size();
  });

  last = 0;
  if (tour.size()) {
    // we check to change to the next one
    int bck = tour.back();

    if (d[bck] < d[f[p[1]].back()]) {
      last = 1;
    }
  }

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

  tour.push_back(centroid);

  return tour;
}

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