oj.uz

Submission #1042503

# Submission time Handle Problem Language Result Execution time Memory
1042503 2024-08-03T05:52:06 Z sleepntsheep Inside information (BOI21_servers) C
100 / 100
 1887 ms 29776 KB 
#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], dp[N], counted[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) { /* remove parent from adj */
    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) { /* hld prep */
    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), va, ua;
  va = navigate(a, v);
  ua = navigate(a, u);

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

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

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 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) {
    scanf(" %s%d", qq[i].type, &qq[i].a);
    if (qq[i].type[0] == 'S') {
      scanf("%d", &qq[i].b);
      link(qq[i].a, qq[i].b, j++);
    } else if (qq[i].type[0] == 'Q')
      scanf("%d", &qq[i].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 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(qq[i].a) && query_yesno(qq[i].a, a[ii], j - 1))
              ++addition, counted[a[ii]] = i + 1;
        }
      printf("%d\n", dp[qq[i].a] + addition);
    }
  }
}

Compilation message

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

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 8284 KB Output is correct
2 Correct 73 ms 9556 KB Output is correct
3 Correct 72 ms 9556 KB Output is correct
4 Correct 66 ms 9564 KB Output is correct
5 Correct 57 ms 9812 KB Output is correct
6 Correct 70 ms 9560 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 8284 KB Output is correct
2 Correct 73 ms 9556 KB Output is correct
3 Correct 72 ms 9556 KB Output is correct
4 Correct 66 ms 9564 KB Output is correct
5 Correct 57 ms 9812 KB Output is correct
6 Correct 70 ms 9560 KB Output is correct
7 Correct 56 ms 9048 KB Output is correct
8 Correct 104 ms 9296 KB Output is correct
9 Correct 82 ms 9556 KB Output is correct
10 Correct 76 ms 9556 KB Output is correct
11 Correct 60 ms 9628 KB Output is correct
12 Correct 92 ms 9580 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 8284 KB Output is correct
2 Correct 678 ms 20804 KB Output is correct
3 Correct 645 ms 21044 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 8284 KB Output is correct
2 Correct 678 ms 20804 KB Output is correct
3 Correct 645 ms 21044 KB Output is correct
4 Correct 101 ms 8988 KB Output is correct
5 Correct 867 ms 20948 KB Output is correct
6 Correct 1402 ms 20328 KB Output is correct
7 Correct 1651 ms 20488 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 8156 KB Output is correct
2 Correct 550 ms 29524 KB Output is correct
3 Correct 545 ms 29516 KB Output is correct
4 Correct 272 ms 29520 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 8156 KB Output is correct
2 Correct 550 ms 29524 KB Output is correct
3 Correct 545 ms 29516 KB Output is correct
4 Correct 272 ms 29520 KB Output is correct
5 Correct 48 ms 9100 KB Output is correct
6 Correct 695 ms 29220 KB Output is correct
7 Correct 331 ms 29268 KB Output is correct
8 Correct 780 ms 28752 KB Output is correct
9 Correct 773 ms 28772 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 8280 KB Output is correct
2 Correct 330 ms 20024 KB Output is correct
3 Correct 647 ms 20240 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 8280 KB Output is correct
2 Correct 330 ms 20024 KB Output is correct
3 Correct 647 ms 20240 KB Output is correct
4 Correct 48 ms 9040 KB Output is correct
5 Correct 510 ms 19792 KB Output is correct
6 Correct 1039 ms 19796 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 8236 KB Output is correct
2 Correct 548 ms 29468 KB Output is correct
3 Correct 598 ms 29776 KB Output is correct
4 Correct 330 ms 29488 KB Output is correct
5 Correct 50 ms 9044 KB Output is correct
6 Correct 341 ms 20052 KB Output is correct
7 Correct 636 ms 20236 KB Output is correct
8 Correct 548 ms 21228 KB Output is correct
9 Correct 601 ms 21048 KB Output is correct
10 Correct 585 ms 23640 KB Output is correct
11 Correct 551 ms 22880 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 8236 KB Output is correct
2 Correct 548 ms 29468 KB Output is correct
3 Correct 598 ms 29776 KB Output is correct
4 Correct 330 ms 29488 KB Output is correct
5 Correct 50 ms 9044 KB Output is correct
6 Correct 341 ms 20052 KB Output is correct
7 Correct 636 ms 20236 KB Output is correct
8 Correct 548 ms 21228 KB Output is correct
9 Correct 601 ms 21048 KB Output is correct
10 Correct 585 ms 23640 KB Output is correct
11 Correct 551 ms 22880 KB Output is correct
12 Correct 49 ms 8924 KB Output is correct
13 Correct 645 ms 29264 KB Output is correct
14 Correct 328 ms 29184 KB Output is correct
15 Correct 765 ms 29012 KB Output is correct
16 Correct 727 ms 28752 KB Output is correct
17 Correct 66 ms 9044 KB Output is correct
18 Correct 509 ms 19792 KB Output is correct
19 Correct 1033 ms 19792 KB Output is correct
20 Correct 605 ms 20820 KB Output is correct
21 Correct 959 ms 21076 KB Output is correct
22 Correct 766 ms 22356 KB Output is correct
23 Correct 784 ms 23736 KB Output is correct
24 Correct 708 ms 23600 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 8276 KB Output is correct
2 Correct 74 ms 9592 KB Output is correct
3 Correct 72 ms 9668 KB Output is correct
4 Correct 68 ms 9560 KB Output is correct
5 Correct 66 ms 9964 KB Output is correct
6 Correct 70 ms 9556 KB Output is correct
7 Correct 55 ms 8896 KB Output is correct
8 Correct 657 ms 20920 KB Output is correct
9 Correct 619 ms 21072 KB Output is correct
10 Correct 46 ms 9044 KB Output is correct
11 Correct 545 ms 29524 KB Output is correct
12 Correct 583 ms 29424 KB Output is correct
13 Correct 312 ms 29524 KB Output is correct
14 Correct 62 ms 9048 KB Output is correct
15 Correct 326 ms 20048 KB Output is correct
16 Correct 620 ms 20176 KB Output is correct
17 Correct 534 ms 21300 KB Output is correct
18 Correct 568 ms 21332 KB Output is correct
19 Correct 588 ms 23636 KB Output is correct
20 Correct 551 ms 23252 KB Output is correct
21 Correct 601 ms 21076 KB Output is correct
22 Correct 671 ms 21072 KB Output is correct
23 Correct 738 ms 21588 KB Output is correct
24 Correct 726 ms 21424 KB Output is correct
25 Correct 927 ms 23384 KB Output is correct
26 Correct 654 ms 20256 KB Output is correct
27 Correct 623 ms 20560 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 8276 KB Output is correct
2 Correct 74 ms 9592 KB Output is correct
3 Correct 72 ms 9668 KB Output is correct
4 Correct 68 ms 9560 KB Output is correct
5 Correct 66 ms 9964 KB Output is correct
6 Correct 70 ms 9556 KB Output is correct
7 Correct 55 ms 8896 KB Output is correct
8 Correct 657 ms 20920 KB Output is correct
9 Correct 619 ms 21072 KB Output is correct
10 Correct 46 ms 9044 KB Output is correct
11 Correct 545 ms 29524 KB Output is correct
12 Correct 583 ms 29424 KB Output is correct
13 Correct 312 ms 29524 KB Output is correct
14 Correct 62 ms 9048 KB Output is correct
15 Correct 326 ms 20048 KB Output is correct
16 Correct 620 ms 20176 KB Output is correct
17 Correct 534 ms 21300 KB Output is correct
18 Correct 568 ms 21332 KB Output is correct
19 Correct 588 ms 23636 KB Output is correct
20 Correct 551 ms 23252 KB Output is correct
21 Correct 601 ms 21076 KB Output is correct
22 Correct 671 ms 21072 KB Output is correct
23 Correct 738 ms 21588 KB Output is correct
24 Correct 726 ms 21424 KB Output is correct
25 Correct 927 ms 23384 KB Output is correct
26 Correct 654 ms 20256 KB Output is correct
27 Correct 623 ms 20560 KB Output is correct
28 Correct 47 ms 9040 KB Output is correct
29 Correct 89 ms 9296 KB Output is correct
30 Correct 77 ms 9480 KB Output is correct
31 Correct 77 ms 9456 KB Output is correct
32 Correct 61 ms 9500 KB Output is correct
33 Correct 116 ms 9404 KB Output is correct
34 Correct 52 ms 9040 KB Output is correct
35 Correct 867 ms 20564 KB Output is correct
36 Correct 1492 ms 20460 KB Output is correct
37 Correct 1676 ms 20320 KB Output is correct
38 Correct 47 ms 8960 KB Output is correct
39 Correct 662 ms 29140 KB Output is correct
40 Correct 345 ms 29268 KB Output is correct
41 Correct 779 ms 28744 KB Output is correct
42 Correct 768 ms 28768 KB Output is correct
43 Correct 48 ms 8856 KB Output is correct
44 Correct 529 ms 19908 KB Output is correct
45 Correct 1034 ms 19796 KB Output is correct
46 Correct 656 ms 20836 KB Output is correct
47 Correct 953 ms 20820 KB Output is correct
48 Correct 792 ms 22096 KB Output is correct
49 Correct 786 ms 23824 KB Output is correct
50 Correct 780 ms 21848 KB Output is correct
51 Correct 1401 ms 19352 KB Output is correct
52 Correct 1493 ms 19224 KB Output is correct
53 Correct 1887 ms 19064 KB Output is correct
54 Correct 1451 ms 19248 KB Output is correct
55 Correct 1680 ms 19280 KB Output is correct
56 Correct 1089 ms 19388 KB Output is correct
57 Correct 1196 ms 21020 KB Output is correct
58 Correct 931 ms 18260 KB Output is correct
59 Correct 569 ms 18424 KB Output is correct