제출 #762758

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
762758		vjudge1	Fun Tour (APIO20_fun)	C++17	0 / 100	1 ms	288 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);

  if (n <= 600) {
    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 {
    for (int i = 1; i < n; i++) {
      int x = i;
      int y = (i - 1) / 2;

      adj[x].push_back(y);
      adj[y].push_back(x);
    }
  }

  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 fendPoint = findFarthest(0);
  int sendPoint = findFarthest(fendPoint);

  /*
    contains pairs (depth, node) sorted by non-decreasing depth
  */

  vector<pair<int, int>> st_first;
  vector<pair<int, int>> st_second;

  function<void(int, int, int, bool)> Dfs = [&](int u, int prev, int depth, bool which) {
    if (which) {
      st_second.push_back({depth, u});
    } else {
      st_first.push_back({depth, u});
    }
    
    for (auto v : adj[u]) {
      if (v == prev) {
        continue;
      }

      Dfs(v, u, depth + 1, which);
    }
  };

  Dfs(fendPoint, -1, 0, 0);
  Dfs(sendPoint, -1, 0, 1);

  sort(st_first.begin(), st_first.end());
  sort(st_second.begin(), st_second.end());

  vector<int> perm;
  perm.push_back(fendPoint);
  perm.push_back(sendPoint);
  block[fendPoint] = block[sendPoint] = true;

  for (int it = 0; ; it++) {
    if (it % 2 == 0) {
      while (!st_second.empty()) {
        auto x = st_second.back();

        if (block[x.second]) {
          st_second.pop_back();
        } else {
          perm.push_back(x.second);
          block[x.second] = true;
          st_second.pop_back();
          break;
        }
      }
    } else {
      while (!st_first.empty()) {
        auto x = st_first.back();

        if (block[x.second]) {
          st_first.pop_back();
        } else {
          perm.push_back(x.second);
          block[x.second] = true;
          st_first.pop_back();
          break;
        }

        st_first.pop_back();
      }
    }
    debug(perm);

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

/*

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

  vector<int> res = createFunTour(7, 40000);

  debug(res);
  return 0;
}
*/

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