Submission #115320

#	Time	Username	Problem	Language	Result	Execution time	Memory
115320		model_code	Treasure Hunt (CEOI11_tre)	C++14	50 / 100	1905 ms	262148 KiB

Main

/* Slow solution to the task Treasure hunt
 * Author: Jakub Radoszewski
 * Date: 9.06.2011
 * Time complexity: O((#nodes + #dig) * log(#nodes)).
 * Description: computes LCA in #nodes * log(#nodes) time and space.
 * Constructs the tree explicitly.
 */


#include <utility>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;


#define LOG_MAX_N 31

/* This node will be created if a path call appears */
int curr;



/*****************************************************************************/
/* Utility functions for handling ancestors and lca's. */

vector<vector<int> > anc;
vector<int> depth;

/* Computes anc[a], starting with anc[a][0] = par. */
inline void compute_anc(int a, int par)
{
  anc[a].push_back(par);
  for (int i = 0; i < LOG_MAX_N; i++)
    anc[a].push_back(anc[anc[a][i]][i]);
}

/* Advances h edges up, starting from the node a. */
inline int go_up(int a, int h)
{
  for (int i = 0; i < LOG_MAX_N; i++)
    if (h & (1 << i))
      a = anc[a][i];
  return a;
}

inline int lca(int a, int b)
{
  /* Equalizing depths */
  if (depth[a] < depth[b])
    swap(a, b);
  a = go_up(a, depth[a] - depth[b]);
  if (a == b)
    return a;

  /* Finding LCA */
  int i = 0;
  while (anc[a][i] != anc[b][i])
    i++;
  for (int j = i - 1; j >= 0; j--)
    if (anc[a][j] != anc[b][j])
    {
      a = anc[a][j];
      b = anc[b][j];
    }
  return anc[a][0];
}




/*****************************************************************************/

void init()
{
  depth.push_back(-1); /* node 0 */
  depth.push_back(0); /* node 1 */
  anc.resize(2, vector<int>());
  for (int i = 0; i < LOG_MAX_N; i++)
    anc[1].push_back(1); /* sentinel */
  curr = 2;
}


/*****************************************************************************/

void path(int a, int s)
{
  int prev = a;
  for (int i = 0; i < s; i++)
  {
    depth.push_back(depth[prev] + 1);
    anc.push_back(vector<int>());
    compute_anc(curr, prev);
    prev = curr;
    curr++;
  }
}


/*****************************************************************************/

int dig(int a, int b)
{
  int v = lca(a, b);
  int len = depth[a] + depth[b] - 2 * depth[v];
  int pos = len / 2;
  if (pos <= depth[a] - depth[v])
    return go_up(a, pos);
  else
    return go_up(b, len - pos);
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10