oj.uz

Submission #1042496

# Submission time Handle Problem Language Result Execution time Memory
1042496 2024-08-03T05:43:31 Z sleepntsheep Inside information (BOI21_servers) C
100 / 100
 1500 ms 29780 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], tout[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];
        eh[u][eo[u]] = p;
        fh[u][eo[u]] = ww;
        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;
    if (eo[u])
        efs(eh[u][0], hd);
    for (int j = 1; j < eo[u]; ++j)
        efs(eh[u][j], eh[u][j]);
    tout[u] = timer - 1;
}

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;
    for (int i = 1; i <= n; ++i)
        ds_find(i);

    for (int i = ii; i >= 0; --i) {
        if (qq[i].type[0] != 'S')
            continue;

        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 = qq[k].a, b = qq[k].b;

                    if (counted[a] != i + 1 &&
                            ds[a] != ds[focus] && query_yesno(focus, a, j - 1))
                        ++addition, counted[a] = i + 1;
                    if (counted[b] != i + 1 && 
                            ds[b] != ds[focus] && query_yesno(focus, b, j - 1))
                        ++addition, counted[b] = i + 1;
                }
            printf("%d\n", dp[focus] + addition);
        }
    }
}

Compilation message

servers.c: In function 'pus_':
servers.c:36:26: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   36 |     else if (0 == (o & o - 1)) eh[i] = (int*)realloc(eh[i], 2 * o * sizeof **eh);
      |                        ~~^~~
servers.c: In function 'main':
servers.c:156:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |     scanf("%d%d", &n, &q);
      |     ^~~~~~~~~~~~~~~~~~~~~
servers.c:165:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |         scanf(" %s%d", s, &a);
      |         ^~~~~~~~~~~~~~~~~~~~~
servers.c:167:13: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |             scanf("%d", &b);
      |             ^~~~~~~~~~~~~~~
servers.c:170:13: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |             scanf("%d", &b);
      |             ^~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 6992 KB Output is correct
2 Correct 61 ms 7504 KB Output is correct
3 Correct 68 ms 7572 KB Output is correct
4 Correct 61 ms 7508 KB Output is correct
5 Correct 48 ms 7892 KB Output is correct
6 Correct 56 ms 7424 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 6992 KB Output is correct
2 Correct 61 ms 7504 KB Output is correct
3 Correct 68 ms 7572 KB Output is correct
4 Correct 61 ms 7508 KB Output is correct
5 Correct 48 ms 7892 KB Output is correct
6 Correct 56 ms 7424 KB Output is correct
7 Correct 39 ms 7048 KB Output is correct
8 Correct 81 ms 7428 KB Output is correct
9 Correct 81 ms 7596 KB Output is correct
10 Correct 65 ms 7508 KB Output is correct
11 Correct 48 ms 7764 KB Output is correct
12 Correct 71 ms 7508 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 7004 KB Output is correct
2 Correct 712 ms 19028 KB Output is correct
3 Correct 686 ms 19096 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 7004 KB Output is correct
2 Correct 712 ms 19028 KB Output is correct
3 Correct 686 ms 19096 KB Output is correct
4 Correct 38 ms 7116 KB Output is correct
5 Correct 931 ms 19560 KB Output is correct
6 Correct 1061 ms 19904 KB Output is correct
7 Correct 1428 ms 19744 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 6992 KB Output is correct
2 Correct 629 ms 29268 KB Output is correct
3 Correct 675 ms 29416 KB Output is correct
4 Correct 356 ms 29264 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 6992 KB Output is correct
2 Correct 629 ms 29268 KB Output is correct
3 Correct 675 ms 29416 KB Output is correct
4 Correct 356 ms 29264 KB Output is correct
5 Correct 35 ms 7004 KB Output is correct
6 Correct 652 ms 29580 KB Output is correct
7 Correct 344 ms 29780 KB Output is correct
8 Correct 685 ms 29520 KB Output is correct
9 Correct 688 ms 29520 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 7004 KB Output is correct
2 Correct 367 ms 18068 KB Output is correct
3 Correct 690 ms 18000 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 7004 KB Output is correct
2 Correct 367 ms 18068 KB Output is correct
3 Correct 690 ms 18000 KB Output is correct
4 Correct 37 ms 7004 KB Output is correct
5 Correct 538 ms 18520 KB Output is correct
6 Correct 1020 ms 18352 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 7004 KB Output is correct
2 Correct 613 ms 29432 KB Output is correct
3 Correct 603 ms 29268 KB Output is correct
4 Correct 305 ms 29268 KB Output is correct
5 Correct 46 ms 7248 KB Output is correct
6 Correct 382 ms 18004 KB Output is correct
7 Correct 655 ms 18256 KB Output is correct
8 Correct 594 ms 19280 KB Output is correct
9 Correct 611 ms 19028 KB Output is correct
10 Correct 607 ms 22296 KB Output is correct
11 Correct 573 ms 21328 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 7004 KB Output is correct
2 Correct 613 ms 29432 KB Output is correct
3 Correct 603 ms 29268 KB Output is correct
4 Correct 305 ms 29268 KB Output is correct
5 Correct 46 ms 7248 KB Output is correct
6 Correct 382 ms 18004 KB Output is correct
7 Correct 655 ms 18256 KB Output is correct
8 Correct 594 ms 19280 KB Output is correct
9 Correct 611 ms 19028 KB Output is correct
10 Correct 607 ms 22296 KB Output is correct
11 Correct 573 ms 21328 KB Output is correct
12 Correct 38 ms 6992 KB Output is correct
13 Correct 704 ms 29580 KB Output is correct
14 Correct 337 ms 29776 KB Output is correct
15 Correct 735 ms 29592 KB Output is correct
16 Correct 695 ms 29520 KB Output is correct
17 Correct 39 ms 7004 KB Output is correct
18 Correct 600 ms 18596 KB Output is correct
19 Correct 1047 ms 18220 KB Output is correct
20 Correct 658 ms 19080 KB Output is correct
21 Correct 928 ms 19316 KB Output is correct
22 Correct 761 ms 21584 KB Output is correct
23 Correct 720 ms 23120 KB Output is correct
24 Correct 693 ms 22964 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 7004 KB Output is correct
2 Correct 61 ms 7488 KB Output is correct
3 Correct 62 ms 7508 KB Output is correct
4 Correct 66 ms 7464 KB Output is correct
5 Correct 44 ms 7656 KB Output is correct
6 Correct 64 ms 7556 KB Output is correct
7 Correct 39 ms 7160 KB Output is correct
8 Correct 684 ms 19128 KB Output is correct
9 Correct 704 ms 19284 KB Output is correct
10 Correct 37 ms 6992 KB Output is correct
11 Correct 599 ms 29524 KB Output is correct
12 Correct 623 ms 29268 KB Output is correct
13 Correct 312 ms 29276 KB Output is correct
14 Correct 36 ms 7004 KB Output is correct
15 Correct 372 ms 18064 KB Output is correct
16 Correct 664 ms 18004 KB Output is correct
17 Correct 584 ms 19024 KB Output is correct
18 Correct 622 ms 19024 KB Output is correct
19 Correct 672 ms 22356 KB Output is correct
20 Correct 589 ms 21344 KB Output is correct
21 Correct 693 ms 19028 KB Output is correct
22 Correct 672 ms 19080 KB Output is correct
23 Correct 752 ms 19536 KB Output is correct
24 Correct 785 ms 19460 KB Output is correct
25 Correct 937 ms 21752 KB Output is correct
26 Correct 654 ms 18512 KB Output is correct
27 Correct 621 ms 18584 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 7004 KB Output is correct
2 Correct 61 ms 7488 KB Output is correct
3 Correct 62 ms 7508 KB Output is correct
4 Correct 66 ms 7464 KB Output is correct
5 Correct 44 ms 7656 KB Output is correct
6 Correct 64 ms 7556 KB Output is correct
7 Correct 39 ms 7160 KB Output is correct
8 Correct 684 ms 19128 KB Output is correct
9 Correct 704 ms 19284 KB Output is correct
10 Correct 37 ms 6992 KB Output is correct
11 Correct 599 ms 29524 KB Output is correct
12 Correct 623 ms 29268 KB Output is correct
13 Correct 312 ms 29276 KB Output is correct
14 Correct 36 ms 7004 KB Output is correct
15 Correct 372 ms 18064 KB Output is correct
16 Correct 664 ms 18004 KB Output is correct
17 Correct 584 ms 19024 KB Output is correct
18 Correct 622 ms 19024 KB Output is correct
19 Correct 672 ms 22356 KB Output is correct
20 Correct 589 ms 21344 KB Output is correct
21 Correct 693 ms 19028 KB Output is correct
22 Correct 672 ms 19080 KB Output is correct
23 Correct 752 ms 19536 KB Output is correct
24 Correct 785 ms 19460 KB Output is correct
25 Correct 937 ms 21752 KB Output is correct
26 Correct 654 ms 18512 KB Output is correct
27 Correct 621 ms 18584 KB Output is correct
28 Correct 37 ms 7004 KB Output is correct
29 Correct 78 ms 7504 KB Output is correct
30 Correct 64 ms 7508 KB Output is correct
31 Correct 62 ms 7504 KB Output is correct
32 Correct 47 ms 7648 KB Output is correct
33 Correct 69 ms 7540 KB Output is correct
34 Correct 39 ms 6996 KB Output is correct
35 Correct 890 ms 19536 KB Output is correct
36 Correct 1100 ms 19728 KB Output is correct
37 Correct 1500 ms 19800 KB Output is correct
38 Correct 38 ms 7048 KB Output is correct
39 Correct 752 ms 29520 KB Output is correct
40 Correct 341 ms 29744 KB Output is correct
41 Correct 799 ms 29416 KB Output is correct
42 Correct 745 ms 29564 KB Output is correct
43 Correct 38 ms 7068 KB Output is correct
44 Correct 541 ms 18512 KB Output is correct
45 Correct 1008 ms 18284 KB Output is correct
46 Correct 655 ms 19284 KB Output is correct
47 Correct 930 ms 19280 KB Output is correct
48 Correct 769 ms 21692 KB Output is correct
49 Correct 782 ms 23120 KB Output is correct
50 Correct 729 ms 22876 KB Output is correct
51 Correct 1077 ms 19792 KB Output is correct
52 Correct 1338 ms 20052 KB Output is correct
53 Correct 1437 ms 19716 KB Output is correct
54 Correct 1057 ms 19752 KB Output is correct
55 Correct 1361 ms 19888 KB Output is correct
56 Correct 1086 ms 19976 KB Output is correct
57 Correct 1095 ms 22040 KB Output is correct
58 Correct 891 ms 18768 KB Output is correct
59 Correct 646 ms 18516 KB Output is correct