Submission #1031539

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031539		sleepntsheep	Tourism (JOI23_tourism)	C11	100 / 100	1039 ms	30724 KiB

tourism

#include <stdio.h>
#include <stdlib.h>

void pus_(int **eh, int *eo, int x) {
  int o = eo[0]++;
  if (o == 0)
    eh[0] = (int*)malloc(2 * sizeof **eh);
  else if ((o & (o - 1)) == 0)
    eh[0] = (int*)realloc(eh[0], 2 * o * sizeof **eh);
  eh[0][o++] = x;
}
#define pus(eh, eo, x) pus_(&(eh), &(eo), x)

int min(int i, int j) { return i < j ? i : j; }
int max(int i, int j) { return i > j ? i : j; }

#define QQ 100000
#define NN 100000
#define MM 100000
/*BEGINfenwick*/
int fw[MM];
void fw_add(int p, int k) {
  for (; p < sizeof fw / sizeof *fw; p |= p + 1)
    fw[p] += k;
}
long long fw_sum(int p) {
  long long z = 0;
  for (++p; p > 0; p &= p - 1)
    z += fw[p - 1];
  return z;
}
/*ENDfenwick*/

int tout[NN], Ans[QQ], N, M, Q, C[MM], L[QQ], R[QQ], X[NN], Y[NN], Freq[NN],
    *Occ[NN]; /* Freq[u] = how many k such that C[k] = u , Occ[u] = that list of
                 ks */

/* BEGINoriginal tree*/
int *adj[NN], deg[NN], dfn[NN], timer,
    /*for lca, lca for virtual tree*/ dep[NN], jmp[NN], par[NN];
void tree_link(int u, int v) {
  pus(adj[u], deg[u], v);
}
void tree_link_bi(int u, int v) {
    tree_link(u, v), tree_link(v, u);
}
void dfs(int u, int p) {
  dep[u] = dep[par[u] = p] + 1;
  jmp[u] = (dep[p] - dep[jmp[p]] == dep[jmp[p]] - dep[jmp[jmp[p]]]) ? jmp[jmp[p]] : p;
  dfn[u] = timer++;
  for (int j = 0; j < deg[u]; ++j)
    if (adj[u][j] - p)
      dfs(adj[u][j], u);
  tout[u] = timer - 1;
}
int lca(int u, int v) {
  if (dep[u] < dep[v])
    return lca(v, u);
  while (dep[u] > dep[v])
    u = (dep[jmp[u]] >= dep[v]) ? jmp[u] : par[u];
  while (u - v)
    if (jmp[u] == jmp[v])
      u = par[u], v = par[v];
    else
      u = jmp[u], v = jmp[v];
  return u;
}
/* END original tree*/
/*BEGIN virtual tree */
int *vtadj[NN], *vtw[NN], vtdeg[NN], vtdeg2[NN];
void virtual_link(int u, int v, int w) {
    pus(vtadj[u], vtdeg[u], v);
    pus(vtw[u], vtdeg2[u], w);
}
void virtual_link_bi(int u, int v, int w) { virtual_link(u, v, w), virtual_link(v, u, w); }
/*END virtualt ree*/

/* compare nodes by dfn time */
int Compar_Dfn(const void *i, const void *j) {
  return dfn[*(const int *)i] - dfn[*(const int *)j];
}

/* in virtual tree, lef[u] stores highest k < m such that C[k] == u,
 *              analogously, rgt[u] = stores lowest k > m such that C[k] == u
 * this is needed because, we take edge (x, y, w) in virtual tree (rooted at
 * C[m]) if query_l <= x or query_r >= y
 *
 * note that if u is parent of v in virtual tree, even if v's timer more
 * permissive than u's timer, we need to take v anyway, so a node's timer need
 * to be set at least at strict as it's stricted children
 */
int lef[NN], rgt[NN];
int vt_up[NN]; /*weight of u, par[u] */

int add_all = 0;
/* note on how to build virtual tree - sort all vertices in dfn order, insert
 * lca of every consecutive element, uniqueify the new Vertex List, make the
 * tree?? */
void vtdfs(int u, int p, int pw, int m) {
  add_all += pw;
  vt_up[u] = pw;
  /* find upperbound(Occ[u], m); */
  int lb = -1, ub = Freq[u];
  while (ub - lb > 1) {
    int mid = lb + (ub - lb) / 2;
    if (Occ[u][mid] > m)
      ub = mid;
    else
      lb = mid;
  }
  if (ub < Freq[u])
    rgt[u] = Occ[u][ub];
  if ((ub && Occ[u][--ub] < m) || (ub && Occ[u][--ub] < m))
      lef[u] = Occ[u][ub];

  for (int j = 0; j < vtdeg[u]; ++j)
    if (vtadj[u][j] != p) {
      vtdfs(vtadj[u][j], u, vtw[u][j], m);
      lef[u] = max(lef[u], lef[vtadj[u][j]]);
      rgt[u] = min(rgt[u], rgt[vtadj[u][j]]);
    }
}

int Compar_Queries_QL_Decreasing(const void*a,const void*b) {
    return L[*(const int*)b] - L[*(const int*)a];
}

int Compar_Edges_X_Decreasing(const void*a,const void*b) {
    return lef[*(const int*)b] - lef[*(const int*)a];
}

void rev(int *a, int n) {
    int t;
    for (int l = 0, r = n - 1; l < r; ++l, --r)
        t = a[l], a[l] = a[r], a[r] = t;
}

int mark[NN] = {0}, dnc_timer = 0;
/* store active query for dnc, that is query i which L[i] <= m <= R[i] */
void dnc(
    int l, int r, int *candidates,
    int count_candidates) { /*  calc answer for alll queries containing m */
  if (l >= r)
    return; /* ignore l=r because answer is always 1 (ql==qr)*/
  int m = l + (r - l) / 2;

  /* V = set of vertices in virtual tree , ord = |V| */
  /* build a virtual tree for all node u that some l <= k <= r, C[k] = u */
  /* collect all interested nodes */
  int *V = NULL, ord = 0;
  ++dnc_timer;
  for (int i = l; i <= r; ++i)
    if (dnc_timer != mark[C[i]])
       (mark[C[i]] = dnc_timer),
       pus(V, ord, C[i]);

  qsort(V, ord, sizeof *V, Compar_Dfn);
  for (int orig_ord = ord, lc, i = 1; i < orig_ord; ++i)
    if (dnc_timer != mark[lc = lca(V[i], V[i - 1])])
      pus(V, ord, lc), mark[lc] = dnc_timer;
  qsort(V, ord, sizeof *V, Compar_Dfn);

  /* clear global related to virtual tree */
  for (int i = 0; i < ord; ++i) {
      free(vtadj[V[i]]);
      free(vtw[V[i]]);
      vtadj[V[i]] = vtw[V[i]] = NULL;
      vtdeg[V[i]] = vtdeg2[V[i]] = NULL;
  }

  /* build vt */
  {
    static int stack[NN << 1], top;
    top = 0;
    for (int i = 0; i < ord; ++i) {
      int u = V[i];
      while (top && !(dfn[stack[top - 1]] <= dfn[u] &&
                      tout[u] <= tout[stack[top - 1]]))
        --top;
      if (top)
        virtual_link_bi(stack[top - 1], u, dep[u] - dep[stack[top - 1]]);
      stack[top++] = u;
    }
  }

  /* do dfs on vt to calculate lef and rgt */
  for (int i = 0; i < ord; ++i)
    lef[V[i]] = -2, rgt[V[i]] = 1e9 + 2;

  add_all = 0;
  vtdfs(C[m], -1, 0, m);

  /* collect all active queries, one that contain m (ql <= m <= qr) */
  int *active = NULL, nactive = 0,
      *left = NULL, nleft = NULL,
      *right = 0, nright = 0;
  for (int i = 0; i < count_candidates; ++i) {
    int j = candidates[i];
    if (L[j] <= m && m <= R[j])
      pus(active, nactive, j);
    else if (R[j] < m)
      pus(left, nleft, j);
    else if (L[j] > m)
      pus(right, nright, j);
  }

  /*
   * we add w to queries that ql <= x or y <= qr
   * that is , ql <= x , exclusive or (ql > x and y <= qr)
   * */


  /* sort active by ql */
  /* ql <= x */
  qsort(active, nactive, sizeof(int), Compar_Queries_QL_Decreasing);
  qsort(V, ord, sizeof(int), Compar_Edges_X_Decreasing);

  int pi = 0, sum = 0;
  for (int i = 0; i < nactive; ++i) {
      int qi = active[i];
      while (pi < ord && lef[V[pi]] >= L[qi]) 
          sum += vt_up[V[pi++]];
      Ans[qi] += sum;
  }

  /* mutex, ql > x and y <= qr */
  rev(active, nactive);
  rev(V, ord);
  pi = 0;
  for (int i = 0; i < nactive; ++i) {
      int qi = active[i];
      while (pi < ord && lef[V[pi]] < L[qi])
          fw_add(rgt[V[pi]], vt_up[V[pi]]), ++pi;
      Ans[qi] += fw_sum(R[qi]);
  }

  /* undo all fenwick upd (IM GONNA KILLL MYSELF AG IRUH */
  pi = 0;
  for (int i = 0; i < nactive; ++i) {
      int qi = active[i];
      while (pi < ord && lef[V[pi]] < L[qi])
          fw_add(rgt[V[pi]], -vt_up[V[pi]]), ++pi;
  }

  free(V);
  free(active);

  dnc(l, m, left, nleft);
  dnc(m + 1, r, right, nright);
  free(left);
  free(right);
}

int main() {
  scanf("%d%d%d", &N, &M, &Q);
  for (int i = 1, A, B; i < N; ++i)
    scanf("%d%d", &A, &B), tree_link_bi(A - 1, B - 1);
  dep[0] = 0, jmp[0] = par[0] = 0;
  dfs(0, 0);
  for (int i = 0; i < M; ++i)
    scanf("%d", C + i), --C[i], pus(Occ[C[i]], Freq[C[i]], i);
  int *candidates = (int*)malloc(sizeof*candidates * Q);
  for (int i = 0; i < Q; ++i)
    scanf("%d%d", L + i, R + i), --L[i], --R[i], candidates[i] = i;
  dnc(0, M - 1, candidates, Q);
  for (int i = 0; i < Q; ++i)
      printf("%d\n", Ans[i] + 1);
  free(candidates);
}

/*
 * https://codeforces.com/blog/entry/114003?#comment-1015100
 *
 * DNC
 */

Compilation message (stderr)

tourism.c: In function 'dnc':
tourism.c:168:34: warning: assignment to 'int' from 'void *' makes integer from pointer without a cast [-Wint-conversion]
  168 |       vtdeg[V[i]] = vtdeg2[V[i]] = NULL;
      |                                  ^
tourism.c:195:29: warning: initialization of 'int' from 'void *' makes integer from pointer without a cast [-Wint-conversion]
  195 |       *left = NULL, nleft = NULL,
      |                             ^~~~
tourism.c: In function 'main':
tourism.c:255:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  255 |   scanf("%d%d%d", &N, &M, &Q);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~
tourism.c:257:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  257 |     scanf("%d%d", &A, &B), tree_link_bi(A - 1, B - 1);
      |     ^~~~~~~~~~~~~~~~~~~~~
tourism.c:261:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  261 |     scanf("%d", C + i), --C[i], pus(Occ[C[i]], Freq[C[i]], i);
      |     ^~~~~~~~~~~~~~~~~~
tourism.c:264:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  264 |     scanf("%d%d", L + i, R + i), --L[i], --R[i], candidates[i] = i;
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 41 / 41