oj.uz

Submission #1042499

# Submission time Handle Problem Language Result Execution time Memory
1042499 2024-08-03T05:47:41 Z sleepntsheep Inside information (BOI21_servers) C
100 / 100
 1532 ms 27480 KB 
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

int max(int i, int j) { return i > j ? i : j; }
/*
 * For "Q" queries, use LCA + prefix sum on tree ~ 3O(lgn) [for finding lca and almost-lca]
 *
 * Every B queries of any type, do naive dp on tree (reverse edge order)
 * to find answer for "C" queries  ~ O(n)
 *
 * On "C" queries, use cached answer from above and count all edges that appeared after that (by "Q")
 * ~ O(B lgn)
 *
 *
 * Time complexity = O(N^2 / B) + O(N lgn) + O(N B lgn)
 *
 * Let B = sqrt(N / lgN)
 *
 * Should be able to optimize to O(N^1.5) using https://codeforces.com/blog/entry/71567?mobile=true&locale=en 
 */

#define N 120001
#define B 200

int n, q, pp[N], dd[N], up[N], temp, inc[N],
    tin[N], timer, hld[N], ds[N], sz[N];

int ds_find(int i) { return ds[i] == i ? i : (ds[i] = ds_find(ds[i])); }

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

int *eh[N], *fh[N], eo[N];

void link(int u, int v, int w) {
  pus_(eh, eo, u, v);
  --eo[u];
  pus_(fh, eo, u, w);
  pus_(eh, eo, v, u);
  --eo[v];
  pus_(fh, eo, v, w);
}

void dfs(int u, int p) {
  sz[u] = 1;
  inc[u] = (up[u] > up[p]) + inc[p];
  for (int j = 0; j < eo[u]; ++j) if (eh[u][j] != p) {
    int v = eh[u][j];
    dd[v] = dd[u] + 1;
    pp[v] = u;
    up[v] = fh[u][j];
    dfs(v, u);
    sz[u] += sz[v];
  }

  for (int j = 0; j < eo[u]; ++j) if (eh[u][j] == p) {
    int ww = fh[u][j];
    for (int k = j + 1; k < eo[u]; ++k)
      eh[u][k - 1] = eh[u][k], fh[u][k - 1] = fh[u][k];
    --eo[u];
    break;
  }

  for (int j = 0; j < eo[u]; ++j) {
    int v = eh[u][j];
    if (sz[v] > sz[eh[u][0]]) {
      temp = eh[u][0], eh[u][0] = v, eh[u][j] = temp;
      temp = fh[u][0], fh[u][0] = fh[u][j], fh[u][j] = temp;
    }
  }
}

void efs(int u, int hd) {
  tin[u] = timer++;
  hld[u] = hd;
  for (int j = 0; j < eo[u]; ++j)
    efs(eh[u][j], j ? eh[u][j] : hd);
}

int lca(int u, int v) {
  while (hld[u] != hld[v])
    if (dd[hld[u]] >= dd[hld[v]]) u = pp[hld[u]];
    else v = pp[hld[v]];
  return dd[u] <= dd[v] ? u : v;
}

struct Query {
  char type[2];
  int a, b;
} qq[N * 2];

int navigate(int u, int v) {
  int lb = -1, ub = eo[u];
  while (ub-lb>1){
    int md=lb+(ub-lb)/2;
    if(tin[eh[u][md]]<=tin[v])lb=md;
    else ub=md;
  }
  return eh[u][lb];
}

/* u = data node, v = ask node */
int query_yesno(int u, int v, int time) {
  if (u == v) return 1;
  int a = lca(u, v);
  int va, ua;

  if (u == a) {
    va = navigate(a, v);
    return inc[v] - inc[va] == dd[v] - dd[va] && up[v] <= time;
  }
  if (v == a) {
    ua = navigate(a, u);
    return inc[u] - inc[ua] == 0 && up[ua] <= time;
  }

  va = navigate(a, v);
  ua = navigate(a, u);
  return (dd[v] - dd[va] == inc[v] - inc[va]) && (inc[u] - inc[ua] == 0)
    && up[va] > up[ua] && up[v] <= time;
}

int dp[N];

void build(int ii, int tme) {
  for (int i = 1; i <= n; ++i) dp[i] = 1, ds_find(i);
  for (int i = ii; i >= 0; --i)
    if (qq[i].type[0] == 'S') {
      int x = dp[qq[i].a], y = dp[qq[i].b];
      dp[qq[i].a] += y;
      dp[qq[i].b] += x;
    }
}

int counted[N];

int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; ++i) ds[i] = i;

  q = n + q - 1;
  for (int j = 0, i = 0; i < q; ++i) {
    int a, b = 0;
    char *s = qq[i].type;

    scanf(" %s%d", s, &a);
    if (s[0] == 'S') {
      scanf("%d", &b);
      link(a, b, j++);
    } else if (s[0] == 'Q')
      scanf("%d", &b);

    qq[i].a = a, qq[i].b = b;
  }

  up[1] = 1e9;
  pp[1] = 1;
  dfs(1, 1);
  efs(1, 1);

  build(-1, -1);
  int at = 0;

  for (int j = 0, i = 0; i < q; ++i) {

    if (qq[i].type[0] == 'S')
      ++j;

    if (i % B == 0) {
      for (int k = at; k <= i; ++k)
        if (qq[k].type[0] == 'S')
          ds[ds_find(qq[k].a)] = qq[k].b;
      build(i, j - 1);
      at = i + 1;
    }

    if (qq[i].type[0] == 'Q')
      puts(query_yesno(qq[i].b, qq[i].a, j - 1) ? "yes": "no");
    else if (qq[i].type[0] == 'C') {
      int focus = qq[i].a;
      int addition = 0;
      for (int k = at; k < i; ++k)
        if (qq[k].type[0] == 'S') {
          int a[2] = {qq[k].a, qq[k].b};

          for (int ii = 0; ii < 2; ++ii)
            if (counted[a[ii]] != i + 1 &&
                ds_find(a[ii]) != ds_find(focus) && query_yesno(focus, a[ii], j - 1))
              ++addition, counted[a[ii]] = i + 1;
        }
      printf("%d\n", dp[focus] + addition);
    }
  }
}

Compilation message

servers.c: In function 'pus_':
servers.c:34:24: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   34 |   else if (0 == (o & o - 1)) eh[i] = (int*)realloc(eh[i], 2 * o * sizeof **eh);
      |                      ~~^~~
servers.c: In function 'dfs':
servers.c:62:9: warning: unused variable 'ww' [-Wunused-variable]
   62 |     int ww = fh[u][j];
      |         ^~
servers.c: In function 'main':
servers.c:143:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |   scanf("%d%d", &n, &q);
      |   ^~~~~~~~~~~~~~~~~~~~~
servers.c:151:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |     scanf(" %s%d", s, &a);
      |     ^~~~~~~~~~~~~~~~~~~~~
servers.c:153:7: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 |       scanf("%d", &b);
      |       ^~~~~~~~~~~~~~~
servers.c:156:7: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |       scanf("%d", &b);
      |       ^~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 7000 KB Output is correct
2 Correct 76 ms 7488 KB Output is correct
3 Correct 72 ms 7508 KB Output is correct
4 Correct 68 ms 7508 KB Output is correct
5 Correct 56 ms 7764 KB Output is correct
6 Correct 66 ms 7504 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 7000 KB Output is correct
2 Correct 76 ms 7488 KB Output is correct
3 Correct 72 ms 7508 KB Output is correct
4 Correct 68 ms 7508 KB Output is correct
5 Correct 56 ms 7764 KB Output is correct
6 Correct 66 ms 7504 KB Output is correct
7 Correct 48 ms 7004 KB Output is correct
8 Correct 89 ms 7248 KB Output is correct
9 Correct 76 ms 7508 KB Output is correct
10 Correct 75 ms 7508 KB Output is correct
11 Correct 58 ms 7616 KB Output is correct
12 Correct 81 ms 7512 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 7000 KB Output is correct
2 Correct 620 ms 18592 KB Output is correct
3 Correct 624 ms 18848 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 7000 KB Output is correct
2 Correct 620 ms 18592 KB Output is correct
3 Correct 624 ms 18848 KB Output is correct
4 Correct 56 ms 6992 KB Output is correct
5 Correct 836 ms 18956 KB Output is correct
6 Correct 1093 ms 19288 KB Output is correct
7 Correct 1419 ms 19512 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 7004 KB Output is correct
2 Correct 559 ms 26964 KB Output is correct
3 Correct 552 ms 26960 KB Output is correct
4 Correct 270 ms 27232 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 7004 KB Output is correct
2 Correct 559 ms 26964 KB Output is correct
3 Correct 552 ms 26960 KB Output is correct
4 Correct 270 ms 27232 KB Output is correct
5 Correct 51 ms 6988 KB Output is correct
6 Correct 616 ms 27216 KB Output is correct
7 Correct 323 ms 27472 KB Output is correct
8 Correct 672 ms 27228 KB Output is correct
9 Correct 735 ms 27220 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 7004 KB Output is correct
2 Correct 329 ms 17604 KB Output is correct
3 Correct 640 ms 17748 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 7004 KB Output is correct
2 Correct 329 ms 17604 KB Output is correct
3 Correct 640 ms 17748 KB Output is correct
4 Correct 49 ms 7000 KB Output is correct
5 Correct 572 ms 17992 KB Output is correct
6 Correct 1061 ms 17972 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 94 ms 6996 KB Output is correct
2 Correct 597 ms 26960 KB Output is correct
3 Correct 572 ms 27132 KB Output is correct
4 Correct 294 ms 26960 KB Output is correct
5 Correct 46 ms 7004 KB Output is correct
6 Correct 325 ms 17488 KB Output is correct
7 Correct 640 ms 17560 KB Output is correct
8 Correct 562 ms 18508 KB Output is correct
9 Correct 565 ms 18768 KB Output is correct
10 Correct 557 ms 21312 KB Output is correct
11 Correct 527 ms 20304 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 94 ms 6996 KB Output is correct
2 Correct 597 ms 26960 KB Output is correct
3 Correct 572 ms 27132 KB Output is correct
4 Correct 294 ms 26960 KB Output is correct
5 Correct 46 ms 7004 KB Output is correct
6 Correct 325 ms 17488 KB Output is correct
7 Correct 640 ms 17560 KB Output is correct
8 Correct 562 ms 18508 KB Output is correct
9 Correct 565 ms 18768 KB Output is correct
10 Correct 557 ms 21312 KB Output is correct
11 Correct 527 ms 20304 KB Output is correct
12 Correct 45 ms 7004 KB Output is correct
13 Correct 639 ms 27216 KB Output is correct
14 Correct 322 ms 27468 KB Output is correct
15 Correct 707 ms 27324 KB Output is correct
16 Correct 758 ms 27192 KB Output is correct
17 Correct 50 ms 6992 KB Output is correct
18 Correct 529 ms 18008 KB Output is correct
19 Correct 1038 ms 17880 KB Output is correct
20 Correct 587 ms 18604 KB Output is correct
21 Correct 942 ms 18772 KB Output is correct
22 Correct 747 ms 20720 KB Output is correct
23 Correct 761 ms 23636 KB Output is correct
24 Correct 676 ms 21584 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 6996 KB Output is correct
2 Correct 70 ms 7432 KB Output is correct
3 Correct 70 ms 7460 KB Output is correct
4 Correct 66 ms 7508 KB Output is correct
5 Correct 80 ms 7760 KB Output is correct
6 Correct 74 ms 7508 KB Output is correct
7 Correct 50 ms 7044 KB Output is correct
8 Correct 679 ms 18580 KB Output is correct
9 Correct 618 ms 18512 KB Output is correct
10 Correct 60 ms 7000 KB Output is correct
11 Correct 549 ms 26960 KB Output is correct
12 Correct 578 ms 27144 KB Output is correct
13 Correct 275 ms 26912 KB Output is correct
14 Correct 46 ms 7052 KB Output is correct
15 Correct 319 ms 17572 KB Output is correct
16 Correct 641 ms 17744 KB Output is correct
17 Correct 529 ms 18512 KB Output is correct
18 Correct 595 ms 18768 KB Output is correct
19 Correct 585 ms 21164 KB Output is correct
20 Correct 543 ms 20576 KB Output is correct
21 Correct 644 ms 18512 KB Output is correct
22 Correct 652 ms 18504 KB Output is correct
23 Correct 707 ms 18924 KB Output is correct
24 Correct 773 ms 19024 KB Output is correct
25 Correct 869 ms 21084 KB Output is correct
26 Correct 631 ms 17828 KB Output is correct
27 Correct 558 ms 17872 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 6996 KB Output is correct
2 Correct 70 ms 7432 KB Output is correct
3 Correct 70 ms 7460 KB Output is correct
4 Correct 66 ms 7508 KB Output is correct
5 Correct 80 ms 7760 KB Output is correct
6 Correct 74 ms 7508 KB Output is correct
7 Correct 50 ms 7044 KB Output is correct
8 Correct 679 ms 18580 KB Output is correct
9 Correct 618 ms 18512 KB Output is correct
10 Correct 60 ms 7000 KB Output is correct
11 Correct 549 ms 26960 KB Output is correct
12 Correct 578 ms 27144 KB Output is correct
13 Correct 275 ms 26912 KB Output is correct
14 Correct 46 ms 7052 KB Output is correct
15 Correct 319 ms 17572 KB Output is correct
16 Correct 641 ms 17744 KB Output is correct
17 Correct 529 ms 18512 KB Output is correct
18 Correct 595 ms 18768 KB Output is correct
19 Correct 585 ms 21164 KB Output is correct
20 Correct 543 ms 20576 KB Output is correct
21 Correct 644 ms 18512 KB Output is correct
22 Correct 652 ms 18504 KB Output is correct
23 Correct 707 ms 18924 KB Output is correct
24 Correct 773 ms 19024 KB Output is correct
25 Correct 869 ms 21084 KB Output is correct
26 Correct 631 ms 17828 KB Output is correct
27 Correct 558 ms 17872 KB Output is correct
28 Correct 47 ms 7004 KB Output is correct
29 Correct 90 ms 7260 KB Output is correct
30 Correct 75 ms 7508 KB Output is correct
31 Correct 75 ms 7512 KB Output is correct
32 Correct 58 ms 7636 KB Output is correct
33 Correct 94 ms 7560 KB Output is correct
34 Correct 53 ms 7048 KB Output is correct
35 Correct 858 ms 19040 KB Output is correct
36 Correct 1076 ms 19384 KB Output is correct
37 Correct 1410 ms 19280 KB Output is correct
38 Correct 47 ms 6992 KB Output is correct
39 Correct 648 ms 27240 KB Output is correct
40 Correct 321 ms 27480 KB Output is correct
41 Correct 724 ms 27220 KB Output is correct
42 Correct 733 ms 27216 KB Output is correct
43 Correct 49 ms 7004 KB Output is correct
44 Correct 521 ms 17992 KB Output is correct
45 Correct 1018 ms 17868 KB Output is correct
46 Correct 605 ms 18612 KB Output is correct
47 Correct 912 ms 19028 KB Output is correct
48 Correct 759 ms 20676 KB Output is correct
49 Correct 748 ms 23624 KB Output is correct
50 Correct 684 ms 23264 KB Output is correct
51 Correct 1121 ms 21148 KB Output is correct
52 Correct 1348 ms 20796 KB Output is correct
53 Correct 1532 ms 20684 KB Output is correct
54 Correct 1083 ms 21076 KB Output is correct
55 Correct 1395 ms 20892 KB Output is correct
56 Correct 1026 ms 21356 KB Output is correct
57 Correct 1091 ms 22540 KB Output is correct
58 Correct 902 ms 19796 KB Output is correct
59 Correct 574 ms 19844 KB Output is correct