Submission #762827

#	Time	Username	Problem	Language	Result	Execution time	Memory
762827		taher	Fun Tour (APIO20_fun)	C++17	47 / 100	403 ms	97088 KiB

fun

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "C:\GCC\debug.h"
#else
#define debug(...) void(42)
#endif

/*
int hoursRequired(int X, int Y) {
  cout << X << " " << Y << endl;
  int p;
  cin >> p;
  return p;
}
*/

int hoursRequired(int X, int Y);
int attractionsBehind(int X, int Y);

vector<int> createFunTour(int N, int Q) {
  int n = N;

  vector<vector<int>> adj(n);

  bool isBinaryTree = false;

  if (n <= 500) {
    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
        if (hoursRequired(i, j) == 1) {
          adj[i].push_back(j);
          adj[j].push_back(i);
        }
      }
    }
  } else {
    isBinaryTree = true;

    vector<int> par(n, -1);

    for (int i = 1; i < n; i++) {
      int x = i;
      int y = (i - 1) / 2;
      adj[y].push_back(x);
      par[x] = y;
    }

    for (int i = 0; i < n; i++) {
      sort(adj[i].begin(), adj[i].end());
    }
    vector<set<pair<int, int>>> depths(n);
    
    function<void(int)> Dfs = [&](int u) {
      depths[u].insert({0, u});
      for (auto v : adj[u]) {
        Dfs(v);

        for (auto it : depths[v]) {
          depths[u].insert({it.first + 1, it.second});
        }
      }
      return ;
    };
    Dfs(0);


    function<int(int)> GrabLeft = [&](int u) {
      int ret = u;
      for (auto v : adj[u]) {
        ret = GrabLeft(v);
        break;
      }
      return ret;
    };
    vector<int> block(n);

    auto Update = [&](int x) {
      int cnt = 0;
      int ori = x;
      while (x != -1) {
        depths[x].erase({cnt, ori});
        ++cnt;
        x = par[x];
      }
    };

    auto Farthest = [&](int x) {
      x = par[x];
      pair<int, int> best = *prev(depths[x].end());

      int cnt = 0;
      int come = x;
      x = par[x];
      ++cnt;
      while (x != -1) {
        debug(x);
        for (auto v : adj[x]) {
          if (v == come || block[v]) {
            continue;
          }


          if (best.first < cnt + 1 + (*prev(depths[v].end())).first) {
            best.first = cnt + 1 + (*prev(depths[v].end())).first;
            best.second = (*prev(depths[v].end())).second;
          }
        }

        ++cnt;
        come = x;
        x = par[x];
      }
      debug(best);
      return best.second;
    };

    vector<int> perm;
    int start = GrabLeft(0);
    perm.push_back(start);
    block[start] = true;
    Update(start);

    for (int it = 0; ; it++) {
      int nxt = Farthest(start);
      debug(start, nxt);
      debug(start, nxt);
      perm.push_back(nxt);
      debug(perm);
      block[nxt] = true;

      Update(nxt);


      if ((int) perm.size() == n) {
        break;
      }

      swap(nxt, start);
    }

    return perm;
  }

  vector<bool> block(n);

  auto findFarthest = [&](int x) {
    vector<int> d(n, -1);
    d[x] = 0;
    queue<int> que;
    que.push(x);

    while (!que.empty()) {
      auto u = que.front();
      que.pop();

      for (auto v : adj[u]) {
        if (d[v] == -1 && !block[v]) {
          d[v] = d[u] + 1;
          que.push(v);
        }
      }
    }
    return max_element(d.begin(), d.end()) - d.begin();
  };

  int p = findFarthest(0);
  vector<int> perm;

  perm.push_back(p);
  block[p] = true;

  while ((int) perm.size() < n) {
    int nxt = findFarthest(p);
    block[nxt] = true;

    perm.push_back(nxt);
    swap(p, nxt);
  }
  return perm;
}

/*
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  return 0;
}
*/

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:28:8: warning: variable 'isBinaryTree' set but not used [-Wunused-but-set-variable]
   28 |   bool isBinaryTree = false;
      |        ^~~~~~~~~~~~

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