Submission #961887

#	Time	Username	Problem	Language	Result	Execution time	Memory
961887		kilkuwu	Fun Tour (APIO20_fun)	C++17	31 / 100	103 ms	18520 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;
    }
  }
  
  clog << centroid << std::endl;
  
  assert(centroid != -1);

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

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

  std::vector<int> adj;

  for (int i = 1; i < N; i++) {
    if (dist[i].first == 1) {
      adj.push_back(dist[i].second);
    }
  }

  // now we know that
  
  std::vector<std::vector<int>> nodes(adj.size());

  std::vector<int> belong(N, -1);

  for (int i = 0; i + 1 < (int) adj.size(); i++) {
    int u = adj[i];
    for (int j = 0; j < N; j++) {
      if (j == u) {
        belong[j] = i;
        continue;
      }
      if (j == centroid) continue;
      int v = hoursRequired(u, j);
      if (v + 1 == d[j]) {
        belong[j] = i;
      }
    }
  }

  for (int j = 0; j < N; j++) {
    if (j == centroid) continue;
    if (belong[j] == -1) {
      belong[j] = adj.size() - 1;
    }

    nodes[belong[j]].emplace_back(j);
  }

  int sz = nodes.size();
  std::sort(nodes.begin(), nodes.end(), [&](const std::vector<int>& a, const std::vector<int>& b) {
    return a.size() > b.size();
  });

  if (sz == 3 && nodes[0].size() == nodes[1].size() + nodes[2].size()) {
    nodes[1].insert(nodes[1].end(), nodes[2].begin(), nodes[2].end());
    nodes.pop_back();
    sz--;
  }

  for (int i = 0; i < sz; i++) {
    for (int u : nodes[i]) {
      belong[u] = i;
    }
    std::sort(nodes[i].begin(), nodes[i].end(), [&](int x, int y) { return d[x] < d[y]; });
  }


  auto orig = nodes;

  std::vector<int> tour = {nodes[0].back()};
  for (int i = 1; i < sz; i++) {
    if (d[nodes[i].back()] > d[tour[0]]) {
      tour[0] = nodes[i].back();
    }
  }

  nodes[belong[tour[0]]].pop_back();

  auto merge = [&](int i, int j) {
    int rem = 0 ^ 1 ^ 2 ^ i ^ j;
    auto lmao = nodes[rem];
    std::vector<int> ok = nodes[i];
    ok.insert(ok.end(), nodes[j].begin(), nodes[j].end());
    nodes.clear();
    nodes.push_back(ok);
    nodes.push_back(lmao);

    for (int i : nodes[0]) belong[i] = 0;
    for (int j : nodes[1]) belong[j] = 1;
    sz = 2;
    for (int i = 0; i < sz; i++) {
      std::sort(nodes[i].begin(), nodes[i].end(), [&](int x, int y) { return d[x] < d[y]; });
    }
  };

  for (int i = 1; i < N - 1; i++) {
    int v = belong[tour.back()];

    if (sz == 2) {
      v ^= 1;
      tour.push_back(nodes[v].back());
      nodes[v].pop_back();
      continue;
    }

    std::vector<int> rem(3);
    for (int i = 0; i < 3; i++) {
      rem[i] = i;
    }
    rem.erase(rem.begin() + v);

    if (nodes[v].size() + nodes[rem[0]].size() == nodes[rem[1]].size()) {
      merge(v, rem[0]);
      v = 1;
    } else if (nodes[v].size() + nodes[rem[1]].size() == nodes[rem[0]].size()) {
      merge(v, rem[1]);
      v = 1;
    } else {
      v = rem[(d[nodes[rem[0]].back()] < d[nodes[rem[1]].back()])];
    }

    tour.push_back(nodes[v].back());
    nodes[v].pop_back();
  }

  tour.push_back(centroid);
  return tour;
}

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