답안 #115316

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
115316 2019-06-06T17:18:50 Z model_code Treasure Hunt (CEOI11_tre) C
컴파일 오류
0 ms 0 KB
/* Model solution to the task Treasure hunt
 * Author: Jakub Radoszewski
 * Date: 10.06.2011
 * Time complexity: O(#calls * log(#calls)).
 * Description: the explicit nodes are renumbered.
 */


#define MAX_CALLS 400000
#define LOG_2_MAX_CALLS 20

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



/*****************************************************************************/
/* Data structures */


/* An (implicit or explicit) node located dist units below the explicit node
 * expl. */
typedef struct
{
  int expl, dist;
} node;

typedef struct
{
  int node, dist;
} ancestor;

/* The ancestors of the nodes (anc[v][i] is the ancestor 2^i edges above)
 * and their depths. */
ancestor anc[2 * MAX_CALLS][LOG_2_MAX_CALLS];

/* depth includes implicit nodes, real_depth considers only explicit nodes. */
int depth[2 * MAX_CALLS], real_depth[2 * MAX_CALLS];

/* If v is the upper end of an edge, attached[v] is the node to which
 * it is directly attached. Otherwise attached[v].node == -1. */
node attached[2 * MAX_CALLS];

typedef struct
{
  int first, second;
} pair;

/* If expl_anc contains a pair (y, x) then x is the explicit ancestor of
 * all the nodes x..y.
 * Initially the vector contains sentinel pairs (0, 0) and (1, 1). */
pair expl_anc[2 * MAX_CALLS];
int expl_anc_size;


/*****************************************************************************/
/* Simple utility functions */


pair make_pair(int a, int b)
{
  pair p;
  p.first = a;
  p.second = b;
  return p;
}

/* From a renumbered node to the real node value. */
int real_node(int a)
{
  return expl_anc[a].second;
}

int get_depth(node a)
{
  return depth[a.expl] + a.dist;
}

node get_node(int a)
{
  node v;
  int l, h;
  l = 0;
  h = expl_anc_size - 1;
  while (l < h)
  {
    int c;
    c = (l + h) / 2;
    if (expl_anc[c].first < a)
      l = c + 1;
    else
      h = c;
  }
  v.expl = l;
  v.dist = a - real_node(v.expl);
  return v;
}



/*****************************************************************************/
/* Important utility functions */

/* Computes anc[a], starting with anc[a][0] = par. */
void compute_anc(int a, int par, int len)
{
  ancestor v;
  int i;
  v.node = par;
  v.dist = len;
  anc[a][0] = v;
  for (i = 0; i < LOG_2_MAX_CALLS; i++)
  {
    v.node = anc[anc[a][i].node][i].node;
    v.dist = anc[a][i].dist + anc[anc[a][i].node][i].dist;
    anc[a][i + 1] = v;
  }
}


/* Auxiliary function, only on explicit nodes. */
node go_up_aux(int a, int h)
{
  /* Finding the highest explicit node located at most h units above a. */
  int i = 0;
  node b, p;
  while (i + 1 < LOG_2_MAX_CALLS && anc[a][i + 1].dist <= h)
    i++;
  while (i >= 0)
  {
    ancestor p;
    p = anc[a][i];
    if (p.dist <= h)
    {
      h -= p.dist;
      a = p.node;
    }
    i--;
  }

  /* The final touch: finding the potentially implicit node. */
  if (!h)
  {
    b.expl = a;
    b.dist = 0;
    return b;
  }
  p = attached[a];
  if (p.expl == -1) /* a is the lower end of its edge */
  {
    b.expl = anc[a][0].node;
    b.dist = (real_node(a) - real_node(b.expl)) - h;
  } else /* a is the upper end of its edge */
  {
    h--;
    b.expl = p.expl;
    b.dist = p.dist - h;
  }
  return b;
}

/* Advances the distance h up, starting from the node a. */
node go_up(node a, int h)
{
  if (h <= a.dist)
  {
    node b;
    b = a;
    b.dist = a.dist - h;
    return b;
  }
  return go_up_aux(a.expl, h - a.dist);
}

/* Advances h explicit edges up, starting from the node a. */
int go_up_real(int a, int h)
{
  int i;
  i = 0;
  while ((1 << (i + 1)) <= h)
    i++;
  while (h)
  {
    if ((1 << i) <= h)
    {
      a = anc[a][i].node;
      h -= (1 << i);
    }
    i--;
  }
  return a;
}

/* O(log(n)) time */
node lca(node a, node b)
{
  int da, db, i;
  node p, q, res;

  /* Equalizing depths */
  da = real_depth[a.expl]; db = real_depth[b.expl];
  if (da < db || (da == db && a.dist < b.dist))
  {
    p = a; a = b; b = p;
    i = da; da = db; db = i;
  }
  if (a.expl == b.expl)
    return b;
  a.dist = 0;
  if (da > db)
  {
    a.expl = go_up_real(a.expl, da - db - 1);
    if (anc[a.expl][0].node == b.expl)
    {
      node c = attached[a.expl];
      if (c.expl == -1)
        c = b;
      if (c.dist <= b.dist)
        return c;
      else
        return b;
    }
    a.expl = anc[a.expl][0].node;
  }
  b.dist = 0;

  /* Finding LCA */
  i = 0;
  while (anc[a.expl][i].node != anc[b.expl][i].node)
    i++;
  i--;
  while (i >= 0)
  {
    a.expl = anc[a.expl][i].node;
    b.expl = anc[b.expl][i].node;
    while (i >= 0 && anc[a.expl][i].node == anc[b.expl][i].node)
      i--;
  }

  p = attached[a.expl];
  q = attached[b.expl];
  if (p.expl == -1 || q.expl == -1)
  {
    res = p;
    if (res.expl == -1)
      res = q;
    if (res.expl == -1)
    {
      res.expl = anc[a.expl][0].node;
      res.dist = 0;
    }
  } else
  {
    res.expl = anc[a.expl][0].node;
    res.dist = p.dist;
    if (q.dist < p.dist)
      res.dist = q.dist;
  }
  return res;
}




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

void init()
{
  ancestor a;
  int i;

  depth[0] = real_depth[0] = -1;
  depth[1] = real_depth[1] = 0;
  a.node = 1;
  a.dist = 0;
  for (i = 0; i < LOG_2_MAX_CALLS; i++)
    anc[1][i] = a; /* sentinel */
  expl_anc[expl_anc_size++] = make_pair(0, 0);
  expl_anc[expl_anc_size++] = make_pair(1, 1);
  curr = 2;
}


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

void path(int a, int s)
{
  int real_start, real_end, start, end;
  node v;

  v = get_node(a);
  real_start = curr;
  real_end = curr + s - 1;
  start = expl_anc_size;
  end = start;
  if (real_start != real_end)
    end++;

  depth[start] = depth[v.expl] + v.dist + 1;
  real_depth[start] = real_depth[v.expl] + 1;
  if (start != end)
  {
    depth[end] = depth[start] + s - 1;
    real_depth[end] = real_depth[start] + 1;
  }
  compute_anc(start, v.expl, v.dist + 1);
  if (start != end)
    compute_anc(end, start, s - 1);
  attached[start] = v;
  if (start != end)
    attached[end].expl = -1;
  if (start != end)
    expl_anc[expl_anc_size++] = make_pair(real_end - 1, real_start);
  expl_anc[expl_anc_size++] = make_pair(real_end, real_end);
  curr = real_end + 1;
}


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

int dig(int a, int b)
{
  node na, nb, v, res;
  int da, db, dv, len, pos;

  na = get_node(a);
  nb = get_node(b);
  v = lca(na, nb);
  da = depth[na.expl] + na.dist;
  db = depth[nb.expl] + nb.dist;
  dv = depth[v.expl] + v.dist;

  len = da + db - 2 * dv;
  pos = len / 2;
  if (pos <= da - dv)
    res = go_up(na, pos);
  else
    res = go_up(nb, len - pos);
  return real_node(res.expl) + res.dist;
}

Compilation message

tregrader.c:9:10: fatal error: cassert: No such file or directory
 #include <cassert>
          ^~~~~~~~~
compilation terminated.