Submission #1031109

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031109		sleepntsheep	Tourism (JOI23_tourism)	C11	0 / 100	753 ms	16728 KiB

tourism

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

int *mem(int i) { return (int *)calloc(i, sizeof(int)); }
int *remem(int *e, int i) { return (int*)realloc(e, sizeof(int) * i); }
void pus_(int **eh, int *eo, int x) {
  int o = eo[0]++;
  if (o == 0)
    eh[0] = mem(2);
  else if ((o & (o - 1)) == 0)
    eh[0] = remem(eh[0], 2 * o);
  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
#define EE_ (2 * NN)
#define NN_ 100005
/*BEGINfenwick*/
int fw[NN_];
void upd(int p, int k) {
  for (; p < NN_; p |= p + 1)
    fw[p] += k;
}
long long qry(int p) {
  if (p >= NN_)
    p = NN_ - 1;
  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];
int ii, 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 C2(const void *i, const void *j) {
  return lef[*(const int *)i] - lef[*(const int *)j];
}
int C3(const void *i, const void *j) {
  return L[*(const int *)i] - R[*(const int *)j];
}

long long 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] - 1;
  if (ub) {
    if (Occ[u][--ub] < m)
      lef[u] = Occ[u][ub] + 1;
    else if (ub && Occ[u][--ub] < m)
      lef[u] = Occ[u][ub] + 1;
  }

  //printf(" At %d, LR = %d %d\n",u,lef[u],rgt[u]);
  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 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) {
      free(candidates);
    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]]);
      vtdeg[V[i]] = vtdeg2[V[i]] = 0;
  }


  /* 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);

  //printf(" HERE ! %d %d\n", l, r); printf(" Current |V| = %d\n", ord); printf("  : ");for(int i=0;i<ord;++i)printf(" %d : L = %d, R = %d\n", V[i],lef[V[i]],rgt[V[i]]);puts("");




  /* collect all active queries, one that contain m (ql <= m <= qr) */
  int *active = 0, nactive = 0, *left = 0, nleft = 0, *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);
  }
  free(candidates);

  //printf (" Active queries (%d): ",nactive); for (int i=0;i<nactive;++i)printf("%d ",active[i]);puts("");

  /* do fenwick to get answers */
  /* for each node that is not C[m], the edge about it has (x, y, w)
   * add w to each active querys, except ones that x < ql and qr < y
   * by adding 1 to x, -1 to y
   * that is add -w to the one that [x, y]  cover [ql,qr]
   * this can be done with sweepline (wtf)
   *
   * have a sum fenwick tree
   * sort those (x, y, w) edges by increasing x [C2]
   * also sort active querys by increasing ql [C3]
   * do two pointer, and on edges, update -w to y,
   * on queries, add sumfenwick(qr, N) to Ans[query]
   */
  qsort(V, ord, sizeof *V, C2);
  qsort(active, nactive, sizeof *active, C3);
  int pi = 0, qi;
  for (int i = 0; i < nactive; ++i) {
    qi = active[i];
    for (; pi < ord && lef[V[pi]] <= L[qi]; ++pi)
        if (rgt[V[pi]] < 1e9)
            upd(rgt[V[pi]], -vt_up[V[pi]]);
    Ans[qi] += qry(NN_ - 1) - qry(R[qi] - 1);
    Ans[qi] += add_all;
  }

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

  free(V);
  free(active);

  /* continue dnc */
  /* left = queries i in active such that R[i] < m,
   * right = queries i in active such that L[i] > m; */
  dnc(l, m, left, nleft);
  dnc(m + 1, r, right, nright);
  /* dont need to free left and right, since dnc() owns pointers */
}

int main() {
  scanf("%d%d%d", &N, &M, &Q);
  for (int i = 1, A, B; i < N; ++i)
    scanf("%d%d", &A, &B), --A, --B, tree_link_bi(A, B);
  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 = NULL, ncandidates = 0;
  for (int i = 0; i < Q; ++i)
    scanf("%d%d", L + i, R + i), --L[i], --R[i],
        pus(candidates, ncandidates, i);
  dnc(0, M - 1, candidates, ncandidates);
  for (int i = 0; i < Q; ++i)
      printf("%d\n", Ans[i] + 1);
}

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

Compilation message (stderr)

tourism.c: In function 'main':
tourism.c:267:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  267 |   scanf("%d%d%d", &N, &M, &Q);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~
tourism.c:269:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  269 |     scanf("%d%d", &A, &B), --A, --B, tree_link_bi(A, B);
      |     ^~~~~~~~~~~~~~~~~~~~~
tourism.c:273:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  273 |     scanf("%d", C + i), --C[i], pus(Occ[C[i]], Freq[C[i]], i);
      |     ^~~~~~~~~~~~~~~~~~
tourism.c:276:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  276 |     scanf("%d%d", L + i, R + i), --L[i], --R[i],
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~

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