Submission #198420

#	Time	Username	Problem	Language	Result	Execution time	Memory
198420		model_code	Traffickers (RMI18_traffickers)	C++14	60 / 100	3582 ms	29560 KiB

traffickers

/**
 * Description: Split tree in blocks of size sqrt(N) by introducing
 * supplemental vertices. Guarantees O(sqrt(N)) for all queries.
 *
 * Author: Catalin Francu
 **/
#include <math.h>
#include <stdio.h>

#define MAX_N 30000
#define MAX_D 20
#define NIL -1

typedef unsigned short u16;

typedef struct {
  int node, next;
} cell;

cell c[3 * MAX_N];
int head[2 * MAX_N], tail[2 * MAX_N]; /* adjacency lists */
int d[2 * MAX_N]; /* vertex depths */
int p[2 * MAX_N]; /* parents */
int ba[2 * MAX_N]; /* block ancestors */
int n, supn;
int unused; /* pointer to first unused position in c */

/* Variables for cargo info. cargo[d][mod][u] stores the number of units */
/* at times of the form dk+mod for ALL vertices between u (inclusively) */
/* and the block ancestor of u (exclusively) */
int cbuffer[(MAX_D + 1) * MAX_D * MAX_N];
int *cargo[MAX_D + 1][MAX_D]; /* entry points into cbuffer */

/* precompute the (D + 1 choose 2) offsets of cargo arrays, so that we */
/* don't waste half the space */
void initCargo() {
  int *ptr = cbuffer;
  for (int d = 1; d <= MAX_D; d++) {
    for (int i = 0; i < d; i++) {
      cargo[d][i] = ptr;
      ptr += 2 * n;
    }
  }
}

/* add v to u's adjacency list */
void addEdge(int u, int v) {
  c[unused].node = v;
  c[unused].next = NIL;
  if (head[u] == NIL) {
    head[u] = unused;
  } else {
    c[tail[u]].next = unused;
  }
  tail[u] = unused++;
}

void readTree() {
  int u, v;

  scanf("%d", &n);
  supn = n;

  for (u = 0; u < n; u++) {
    head[u] = tail[u] = NIL;
  }

  for (int i = 0; i < n - 1; i++) {
    scanf("%d%d", &u, &v);
    u--; v--;      /* zero-based vertices */
    addEdge(u, v);
    addEdge(v, u);
  }
}

/* removes the child pointed at by ptr from the adjacency list of u */
void removeChild(int u, int ptr, int prev) {
  if (ptr == head[u]) {
    head[u] = c[ptr].next;
  } else {
    c[prev].next = c[ptr].next;
  }

  if (ptr == tail[u]) {
    tail[u] = prev;
  }
}

/* move u's children, up to and including ptr, to a supplemental vertex */
/* this can actually create blocks of size 2 * blockSize */
void moveChildren(int u, int ptr) {
  addEdge(u, supn);

  /* pointers */
  head[supn] = head[u];
  tail[supn] = ptr;
  head[u] = c[ptr].next;
  c[ptr].next = NIL;

  /* depth */
  d[supn] = 1 + d[u];

  /* parents */
  p[supn] = u;
  for (int i = head[supn]; i != NIL; i = c[i].next) {
    p[c[i].node] = supn;
  }

  supn++;
}

/* to avoid some corner cases, put a supplemental node above the root */
void fakeRoot() {
  head[supn] = tail[supn] = NIL;
  addEdge(supn, 0);
  p[0] = supn;
  p[supn] = NIL;
  d[supn] = 0;
  supn++;
}

/* (1) compute depths and parents */
/* (2) remove parents from neighbor lists to obtain proper child lists */
/* (3) insert vertices to split the tree into blocks of size blockSize */
/* returns the number of vertices not yet assigned to a block */
int depthDfs(int u, int parent, int depth, int blockSize) {
  d[u] = depth;
  p[u] = parent;

  int ptr = head[u], prev = NIL, result = 0;
  while (ptr != NIL && c[ptr].node < n) { /* supplementary vertices are at the end */
    if (c[ptr].node == parent) {
      /* remove parent from neighbor list */
      removeChild(u, ptr, prev);
      ptr = c[ptr].next;     /* prev stays the same */
    } else {
      result += depthDfs(c[ptr].node, u, depth + 2, blockSize);

      if (result >= blockSize) {
        moveChildren(u, ptr);
        prev = NIL;
        ptr = head[u];
        result = 0;
      } else {
        prev = ptr;
        ptr = c[ptr].next;
      }
    }
  }

  return 1 + result; /* include u itself */
}

/* compute the block ancestor of each vertex; returns the number of
   descendants not assigned to a block */
void blockAncestorDfs(int u, int ancestor) {
  ba[u] = ancestor;
  if (u >= n) {
    ancestor = u;
  }

  for (int ptr = head[u]; ptr != NIL; ptr = c[ptr].next) {
    blockAncestorDfs(c[ptr].node, ancestor);
  }
}

int lca(int u, int v) {
  /* block by block */
  while (ba[u] != ba[v]) {
    if (d[ba[u]] > d[ba[v]]) {
      u = ba[u];
    } else {
      v = ba[v];
    }
  }

  /* vertex by vertex */
  while (u != v) {
    if (d[u] > d[v]) {
      u = p[u];
    } else {
      v = p[v];
    }
  }

  /* if the LCA is a supplemental node, move above it */
  return (u >= n) ? p[u] : u;
}

/* add value to cargo[dist][mod] to all the descendants of u in the same */
/* block as u */
void addTraffickerDfs(int u, int dist, int mod, int value) {
  for (int j = mod; j < dist; j++) {
    cargo[dist][j][u] += value;
  }

  if (u < n) { /* cutoff at supplemental vertices */
    for (int ptr = head[u]; ptr != NIL; ptr = c[ptr].next) {
      addTraffickerDfs(c[ptr].node, dist, mod, value);
    }
  }
}

/* Add a trafficker on the [u, v) path, where v is an ancestor of u or NIL. */
/* At vertex u the trafficker delivers at times of the form dist * k + mod. */
/* At each subsequent vertex the times are incremented by step. */
void addTraffickerPath(int u, int v, int dist, int mod, int step, int value) {
  while (u != v) {
    if (u < n) {
      addTraffickerDfs(u, dist, mod, value);
      mod += step;
    }
    u = p[u];
  }
}

void addTrafficker(int u, int v, int value) {
  int l = lca(u, v);
  int dist = (d[u] + d[v] - 2 * d[l]) / 2 + 1;
  addTraffickerPath(u, p[l], dist, 0, +1, value);
  addTraffickerPath(v, l, dist, dist - 1, -1, value);
}

/* how many traffickers deliver goods on the path u -> root inclusively, */
/* betweeen 0 and t inclusively? */
long long countRoot(int u, int t) {
  long long result = 0;

  while (u != NIL) {
    for (int i = 1; i <= MAX_D; i++) {
      long long lo = cargo[i][t % i][u];
      long long all = cargo[i][i - 1][u];
      result += t / i * all + lo;
    }
    u = ba[u];
  }

  return result;
}

/* how many traffickers deliver goods on the path u -> v inclusively, */
/* betweeen 0 and t inclusively? */
long long countOrigin(int u, int v, int lca, int t) {
  long long result =  countRoot(u, t) + countRoot(v, t) - countRoot(lca, t);
  if (lca) { /* not root */
    result -= countRoot(p[lca], t);
  }
  return result;
}

long long countTraffickers(int u, int v, int t1, int t2) {
  int l = lca(u, v);
  long long result = countOrigin(u, v, l, t2);
  if (t1) {
    result -= countOrigin(u, v, l, t1 - 1);
  }
  return result;
}

int main() {
  readTree();
  initCargo();
  int blockSize = sqrt(n) / 2; /* determined experimentally */
  depthDfs(0, NIL, 1, blockSize);
  fakeRoot();
  blockAncestorDfs(supn - 1, NIL);

  int numQueries, type, u, v, t1, t2;

  /* read the initial traffickers */
  scanf("%d", &numQueries);
  while (numQueries--) {
    scanf("%d%d", &u, &v);
    addTrafficker(u - 1, v - 1, 1);
  }

  /* read the remaining queries */
  scanf("%d", &numQueries);
  while (numQueries--) {
    scanf("%d%d%d", &type, &u, &v);
    if (type == 1) {
      addTrafficker(u - 1, v - 1, 1);
    } else if (type == 2) {
      addTrafficker(u - 1, v - 1, -1);
    } else {
      scanf("%d%d", &t1, &t2);
      long long answer = countTraffickers(u - 1, v - 1,  t1, t2);
      printf("%lld\n", answer);
    }
  }

  return 0;
}

Compilation message (stderr)

traffickers.cpp: In function 'void readTree()':
traffickers.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
traffickers.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &u, &v);
     ~~~~~^~~~~~~~~~~~~~~~
traffickers.cpp: In function 'int main()':
traffickers.cpp:271:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &numQueries);
   ~~~~~^~~~~~~~~~~~~~~~~~~
traffickers.cpp:273:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &u, &v);
     ~~~~~^~~~~~~~~~~~~~~~
traffickers.cpp:278:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &numQueries);
   ~~~~~^~~~~~~~~~~~~~~~~~~
traffickers.cpp:280:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &type, &u, &v);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
traffickers.cpp:286:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d%d", &t1, &t2);
       ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 0 / 40