oj.uz

답안 #1031542

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1031542 2024-07-23T00:10:35 Z sleepntsheep Tourism (JOI23_tourism) C
100 / 100
 1186 ms 29456 KB 
#pragma GCC optimize("O3,unroll-loops")
#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

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;
}

int tout[NN], Ans[QQ], N, M, Q, C[MM], L[QQ], R[QQ], X[NN], Y[NN], Freq[NN], *Occ[NN];

int *adj[NN], deg[NN], dfn[NN], timer, 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;
}

int *vtadj[NN], *vtw[NN], vtdeg[NN], vtdeg2[NN];
void virtual_link(int u, int v, int w) {
  pus(vtadj[u], vtdeg[u], v);
  --vtdeg[u];
  pus(vtw[u], vtdeg[u], w);
}
void virtual_link_bi(int u, int v, int w) {
  virtual_link(u, v, w), virtual_link(v, u, w);
}

int Compar_Dfn(const void *i, const void *j) {
  return dfn[*(const int *)i] - dfn[*(const int *)j];
}

/* in virtual tree, X[u] stores highest k < m such that C[k] == u,
 *              analogously, Y[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 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])
    Y[u] = Occ[u][ub];
  if ((ub && Occ[u][--ub] < m) || (ub && Occ[u][--ub] < m))
    X[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);
      X[u] = max(X[u], X[vtadj[u][j]]);
      Y[u] = min(Y[u], Y[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 X[*(const int *)b] - X[*(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;

void dnc(int l, int r, int *candidates, int count_candidates) {
  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]] = NULL;
    add_all = 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 X and Y */
  for (int i = 0; i < ord; ++i)
    X[V[i]] = -2, Y[V[i]] = 1e9 + 2;

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

  /* collect all active queries, one that contain m (ql <= m <= qr) */
  int *active = NULL, nactive = 0, *Xt = NULL, nXt = 0, *right = NULL,
      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(Xt, nXt, 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 && X[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 && X[V[pi]] < L[qi])
      fw_add(Y[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 && X[V[pi]] < L[qi])
      fw_add(Y[V[pi]], -vt_up[V[pi]]), ++pi;
  }

  free(V);
  free(active);

  dnc(l, m, Xt, nXt);
  dnc(m + 1, r, right, nright);
  free(Xt);
  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);
  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);
  free(candidates);
  for (int i = 0; i < N; ++i)
      free(Occ[i]), free(adj[i]);
  for (int i = 0; i < Q; ++i)
    printf("%d\n", Ans[i] + 1);
  return 0;
}

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

Compilation message

tourism.c: In function 'dnc':
tourism.c:157:17: warning: assignment to 'int' from 'void *' makes integer from pointer without a cast [-Wint-conversion]
  157 |     vtdeg[V[i]] = NULL;
      |                 ^
tourism.c: In function 'main':
tourism.c:239:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  239 |   scanf("%d%d%d", &N, &M, &Q);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~
tourism.c:241:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  241 |     scanf("%d%d", &A, &B), tree_link_bi(A - 1, B - 1);
      |     ^~~~~~~~~~~~~~~~~~~~~
tourism.c:244:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  244 |     scanf("%d", C + i), --C[i], pus(Occ[C[i]], Freq[C[i]], i);
      |     ^~~~~~~~~~~~~~~~~~
tourism.c:247:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  247 |     scanf("%d%d", L + i, R + i), --L[i], --R[i], candidates[i] = i;
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 492 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 516 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 604 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 492 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 516 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 604 KB Output is correct
30 Correct 6 ms 860 KB Output is correct
31 Correct 6 ms 880 KB Output is correct
32 Correct 8 ms 860 KB Output is correct
33 Correct 8 ms 964 KB Output is correct
34 Correct 8 ms 860 KB Output is correct
35 Correct 8 ms 860 KB Output is correct
36 Correct 10 ms 956 KB Output is correct
37 Correct 8 ms 856 KB Output is correct
38 Correct 6 ms 860 KB Output is correct
39 Correct 6 ms 860 KB Output is correct
40 Correct 6 ms 1052 KB Output is correct
41 Correct 6 ms 860 KB Output is correct
42 Correct 6 ms 860 KB Output is correct
43 Correct 6 ms 860 KB Output is correct
44 Correct 7 ms 1256 KB Output is correct
45 Correct 7 ms 860 KB Output is correct
46 Correct 7 ms 860 KB Output is correct
47 Correct 7 ms 996 KB Output is correct
48 Correct 7 ms 860 KB Output is correct
49 Correct 7 ms 860 KB Output is correct
50 Correct 6 ms 996 KB Output is correct
51 Correct 6 ms 860 KB Output is correct
52 Correct 6 ms 860 KB Output is correct
53 Correct 7 ms 860 KB Output is correct
54 Correct 6 ms 976 KB Output is correct
55 Correct 6 ms 860 KB Output is correct
56 Correct 1 ms 604 KB Output is correct
57 Correct 1 ms 604 KB Output is correct
58 Correct 9 ms 980 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 453 ms 16996 KB Output is correct
5 Correct 292 ms 20408 KB Output is correct
6 Correct 437 ms 23724 KB Output is correct
7 Correct 528 ms 27076 KB Output is correct
8 Correct 529 ms 26968 KB Output is correct
9 Correct 543 ms 26836 KB Output is correct
10 Correct 503 ms 26852 KB Output is correct
11 Correct 516 ms 27004 KB Output is correct
12 Correct 291 ms 26616 KB Output is correct
13 Correct 261 ms 26700 KB Output is correct
14 Correct 256 ms 26700 KB Output is correct
15 Correct 32 ms 13904 KB Output is correct
16 Correct 589 ms 27316 KB Output is correct
17 Correct 50 ms 3384 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 381 ms 10904 KB Output is correct
3 Correct 647 ms 12904 KB Output is correct
4 Correct 451 ms 13196 KB Output is correct
5 Correct 704 ms 19060 KB Output is correct
6 Correct 711 ms 19132 KB Output is correct
7 Correct 802 ms 19136 KB Output is correct
8 Correct 767 ms 19132 KB Output is correct
9 Correct 891 ms 19136 KB Output is correct
10 Correct 957 ms 19360 KB Output is correct
11 Correct 975 ms 19412 KB Output is correct
12 Correct 982 ms 19588 KB Output is correct
13 Correct 934 ms 19692 KB Output is correct
14 Correct 926 ms 20156 KB Output is correct
15 Correct 947 ms 21668 KB Output is correct
16 Correct 876 ms 19612 KB Output is correct
17 Correct 915 ms 19544 KB Output is correct
18 Correct 867 ms 19628 KB Output is correct
19 Correct 982 ms 18524 KB Output is correct
20 Correct 954 ms 18528 KB Output is correct
21 Correct 899 ms 18400 KB Output is correct
22 Correct 935 ms 18472 KB Output is correct
23 Correct 963 ms 18656 KB Output is correct
24 Correct 936 ms 18632 KB Output is correct
25 Correct 958 ms 18652 KB Output is correct
26 Correct 968 ms 18944 KB Output is correct
27 Correct 969 ms 18680 KB Output is correct
28 Correct 999 ms 18620 KB Output is correct
29 Correct 1031 ms 18776 KB Output is correct
30 Correct 1014 ms 19028 KB Output is correct
31 Correct 977 ms 19080 KB Output is correct
32 Correct 996 ms 19020 KB Output is correct
33 Correct 1046 ms 19704 KB Output is correct
34 Correct 1186 ms 20916 KB Output is correct

Subtask #5
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 823 ms 14076 KB Output is correct
5 Correct 867 ms 14444 KB Output is correct
6 Correct 951 ms 19220 KB Output is correct
7 Correct 1030 ms 21488 KB Output is correct
8 Correct 967 ms 21484 KB Output is correct
9 Correct 966 ms 21524 KB Output is correct
10 Correct 969 ms 21456 KB Output is correct
11 Correct 996 ms 21552 KB Output is correct
12 Correct 936 ms 21480 KB Output is correct
13 Correct 914 ms 21544 KB Output is correct
14 Correct 51 ms 3360 KB Output is correct

Subtask #6
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 492 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 516 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 604 KB Output is correct
30 Correct 6 ms 860 KB Output is correct
31 Correct 6 ms 880 KB Output is correct
32 Correct 8 ms 860 KB Output is correct
33 Correct 8 ms 964 KB Output is correct
34 Correct 8 ms 860 KB Output is correct
35 Correct 8 ms 860 KB Output is correct
36 Correct 10 ms 956 KB Output is correct
37 Correct 8 ms 856 KB Output is correct
38 Correct 6 ms 860 KB Output is correct
39 Correct 6 ms 860 KB Output is correct
40 Correct 6 ms 1052 KB Output is correct
41 Correct 6 ms 860 KB Output is correct
42 Correct 6 ms 860 KB Output is correct
43 Correct 6 ms 860 KB Output is correct
44 Correct 7 ms 1256 KB Output is correct
45 Correct 7 ms 860 KB Output is correct
46 Correct 7 ms 860 KB Output is correct
47 Correct 7 ms 996 KB Output is correct
48 Correct 7 ms 860 KB Output is correct
49 Correct 7 ms 860 KB Output is correct
50 Correct 6 ms 996 KB Output is correct
51 Correct 6 ms 860 KB Output is correct
52 Correct 6 ms 860 KB Output is correct
53 Correct 7 ms 860 KB Output is correct
54 Correct 6 ms 976 KB Output is correct
55 Correct 6 ms 860 KB Output is correct
56 Correct 1 ms 604 KB Output is correct
57 Correct 1 ms 604 KB Output is correct
58 Correct 9 ms 980 KB Output is correct
59 Correct 0 ms 344 KB Output is correct
60 Correct 0 ms 348 KB Output is correct
61 Correct 1 ms 604 KB Output is correct
62 Correct 453 ms 16996 KB Output is correct
63 Correct 292 ms 20408 KB Output is correct
64 Correct 437 ms 23724 KB Output is correct
65 Correct 528 ms 27076 KB Output is correct
66 Correct 529 ms 26968 KB Output is correct
67 Correct 543 ms 26836 KB Output is correct
68 Correct 503 ms 26852 KB Output is correct
69 Correct 516 ms 27004 KB Output is correct
70 Correct 291 ms 26616 KB Output is correct
71 Correct 261 ms 26700 KB Output is correct
72 Correct 256 ms 26700 KB Output is correct
73 Correct 32 ms 13904 KB Output is correct
74 Correct 589 ms 27316 KB Output is correct
75 Correct 50 ms 3384 KB Output is correct
76 Correct 1 ms 344 KB Output is correct
77 Correct 381 ms 10904 KB Output is correct
78 Correct 647 ms 12904 KB Output is correct
79 Correct 451 ms 13196 KB Output is correct
80 Correct 704 ms 19060 KB Output is correct
81 Correct 711 ms 19132 KB Output is correct
82 Correct 802 ms 19136 KB Output is correct
83 Correct 767 ms 19132 KB Output is correct
84 Correct 891 ms 19136 KB Output is correct
85 Correct 957 ms 19360 KB Output is correct
86 Correct 975 ms 19412 KB Output is correct
87 Correct 982 ms 19588 KB Output is correct
88 Correct 934 ms 19692 KB Output is correct
89 Correct 926 ms 20156 KB Output is correct
90 Correct 947 ms 21668 KB Output is correct
91 Correct 876 ms 19612 KB Output is correct
92 Correct 915 ms 19544 KB Output is correct
93 Correct 867 ms 19628 KB Output is correct
94 Correct 982 ms 18524 KB Output is correct
95 Correct 954 ms 18528 KB Output is correct
96 Correct 899 ms 18400 KB Output is correct
97 Correct 935 ms 18472 KB Output is correct
98 Correct 963 ms 18656 KB Output is correct
99 Correct 936 ms 18632 KB Output is correct
100 Correct 958 ms 18652 KB Output is correct
101 Correct 968 ms 18944 KB Output is correct
102 Correct 969 ms 18680 KB Output is correct
103 Correct 999 ms 18620 KB Output is correct
104 Correct 1031 ms 18776 KB Output is correct
105 Correct 1014 ms 19028 KB Output is correct
106 Correct 977 ms 19080 KB Output is correct
107 Correct 996 ms 19020 KB Output is correct
108 Correct 1046 ms 19704 KB Output is correct
109 Correct 1186 ms 20916 KB Output is correct
110 Correct 0 ms 348 KB Output is correct
111 Correct 0 ms 348 KB Output is correct
112 Correct 2 ms 604 KB Output is correct
113 Correct 823 ms 14076 KB Output is correct
114 Correct 867 ms 14444 KB Output is correct
115 Correct 951 ms 19220 KB Output is correct
116 Correct 1030 ms 21488 KB Output is correct
117 Correct 967 ms 21484 KB Output is correct
118 Correct 966 ms 21524 KB Output is correct
119 Correct 969 ms 21456 KB Output is correct
120 Correct 996 ms 21552 KB Output is correct
121 Correct 936 ms 21480 KB Output is correct
122 Correct 914 ms 21544 KB Output is correct
123 Correct 51 ms 3360 KB Output is correct
124 Correct 825 ms 20516 KB Output is correct
125 Correct 636 ms 18344 KB Output is correct
126 Correct 1081 ms 24172 KB Output is correct
127 Correct 970 ms 24032 KB Output is correct
128 Correct 970 ms 24040 KB Output is correct
129 Correct 970 ms 24032 KB Output is correct
130 Correct 1033 ms 24064 KB Output is correct
131 Correct 818 ms 28484 KB Output is correct
132 Correct 826 ms 29456 KB Output is correct
133 Correct 795 ms 27072 KB Output is correct
134 Correct 1087 ms 23196 KB Output is correct
135 Correct 1126 ms 23188 KB Output is correct
136 Correct 1143 ms 23244 KB Output is correct
137 Correct 605 ms 23952 KB Output is correct
138 Correct 606 ms 23768 KB Output is correct
139 Correct 644 ms 23896 KB Output is correct
140 Correct 552 ms 23792 KB Output is correct
141 Correct 644 ms 23988 KB Output is correct
142 Correct 602 ms 23900 KB Output is correct
143 Correct 70 ms 9300 KB Output is correct
144 Correct 1085 ms 24232 KB Output is correct