oj.uz

Submission #1042495

# Submission time Handle Problem Language Result Execution time Memory
1042495 2024-08-03T05:42:22 Z sleepntsheep Inside information (BOI21_servers) C
100 / 100
 1509 ms 30080 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 37 ms 7000 KB Output is correct
2 Correct 66 ms 7752 KB Output is correct
3 Correct 74 ms 7504 KB Output is correct
4 Correct 56 ms 7520 KB Output is correct
5 Correct 45 ms 7908 KB Output is correct
6 Correct 61 ms 7508 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 7000 KB Output is correct
2 Correct 66 ms 7752 KB Output is correct
3 Correct 74 ms 7504 KB Output is correct
4 Correct 56 ms 7520 KB Output is correct
5 Correct 45 ms 7908 KB Output is correct
6 Correct 61 ms 7508 KB Output is correct
7 Correct 41 ms 6992 KB Output is correct
8 Correct 74 ms 7260 KB Output is correct
9 Correct 67 ms 7648 KB Output is correct
10 Correct 62 ms 7568 KB Output is correct
11 Correct 48 ms 7772 KB Output is correct
12 Correct 76 ms 7588 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 7000 KB Output is correct
2 Correct 723 ms 19160 KB Output is correct
3 Correct 705 ms 19040 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 7000 KB Output is correct
2 Correct 723 ms 19160 KB Output is correct
3 Correct 705 ms 19040 KB Output is correct
4 Correct 42 ms 7000 KB Output is correct
5 Correct 885 ms 19624 KB Output is correct
6 Correct 1165 ms 19816 KB Output is correct
7 Correct 1456 ms 19540 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 7004 KB Output is correct
2 Correct 613 ms 29256 KB Output is correct
3 Correct 639 ms 29300 KB Output is correct
4 Correct 321 ms 29436 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 7004 KB Output is correct
2 Correct 613 ms 29256 KB Output is correct
3 Correct 639 ms 29300 KB Output is correct
4 Correct 321 ms 29436 KB Output is correct
5 Correct 35 ms 7000 KB Output is correct
6 Correct 684 ms 29524 KB Output is correct
7 Correct 340 ms 30080 KB Output is correct
8 Correct 739 ms 29524 KB Output is correct
9 Correct 708 ms 29484 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 6920 KB Output is correct
2 Correct 384 ms 18304 KB Output is correct
3 Correct 713 ms 18128 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 6920 KB Output is correct
2 Correct 384 ms 18304 KB Output is correct
3 Correct 713 ms 18128 KB Output is correct
4 Correct 38 ms 7004 KB Output is correct
5 Correct 609 ms 18308 KB Output is correct
6 Correct 1051 ms 18268 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 7068 KB Output is correct
2 Correct 652 ms 29524 KB Output is correct
3 Correct 597 ms 29292 KB Output is correct
4 Correct 305 ms 29432 KB Output is correct
5 Correct 38 ms 7152 KB Output is correct
6 Correct 371 ms 18236 KB Output is correct
7 Correct 682 ms 18000 KB Output is correct
8 Correct 571 ms 19028 KB Output is correct
9 Correct 664 ms 19248 KB Output is correct
10 Correct 665 ms 22444 KB Output is correct
11 Correct 644 ms 21768 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 7068 KB Output is correct
2 Correct 652 ms 29524 KB Output is correct
3 Correct 597 ms 29292 KB Output is correct
4 Correct 305 ms 29432 KB Output is correct
5 Correct 38 ms 7152 KB Output is correct
6 Correct 371 ms 18236 KB Output is correct
7 Correct 682 ms 18000 KB Output is correct
8 Correct 571 ms 19028 KB Output is correct
9 Correct 664 ms 19248 KB Output is correct
10 Correct 665 ms 22444 KB Output is correct
11 Correct 644 ms 21768 KB Output is correct
12 Correct 71 ms 6992 KB Output is correct
13 Correct 672 ms 29480 KB Output is correct
14 Correct 383 ms 29780 KB Output is correct
15 Correct 725 ms 29580 KB Output is correct
16 Correct 713 ms 29452 KB Output is correct
17 Correct 37 ms 7004 KB Output is correct
18 Correct 559 ms 18444 KB Output is correct
19 Correct 1067 ms 18132 KB Output is correct
20 Correct 671 ms 19200 KB Output is correct
21 Correct 926 ms 19344 KB Output is correct
22 Correct 769 ms 21844 KB Output is correct
23 Correct 770 ms 23124 KB Output is correct
24 Correct 769 ms 22768 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 7152 KB Output is correct
2 Correct 61 ms 7420 KB Output is correct
3 Correct 91 ms 7560 KB Output is correct
4 Correct 57 ms 7648 KB Output is correct
5 Correct 46 ms 7888 KB Output is correct
6 Correct 62 ms 7504 KB Output is correct
7 Correct 38 ms 6992 KB Output is correct
8 Correct 762 ms 19280 KB Output is correct
9 Correct 722 ms 19028 KB Output is correct
10 Correct 39 ms 6992 KB Output is correct
11 Correct 684 ms 29552 KB Output is correct
12 Correct 598 ms 29476 KB Output is correct
13 Correct 305 ms 29440 KB Output is correct
14 Correct 39 ms 6988 KB Output is correct
15 Correct 400 ms 18008 KB Output is correct
16 Correct 708 ms 18224 KB Output is correct
17 Correct 583 ms 19076 KB Output is correct
18 Correct 670 ms 19152 KB Output is correct
19 Correct 631 ms 22356 KB Output is correct
20 Correct 580 ms 21412 KB Output is correct
21 Correct 669 ms 19028 KB Output is correct
22 Correct 677 ms 19024 KB Output is correct
23 Correct 774 ms 19536 KB Output is correct
24 Correct 757 ms 19560 KB Output is correct
25 Correct 939 ms 21840 KB Output is correct
26 Correct 620 ms 18328 KB Output is correct
27 Correct 597 ms 18420 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 7152 KB Output is correct
2 Correct 61 ms 7420 KB Output is correct
3 Correct 91 ms 7560 KB Output is correct
4 Correct 57 ms 7648 KB Output is correct
5 Correct 46 ms 7888 KB Output is correct
6 Correct 62 ms 7504 KB Output is correct
7 Correct 38 ms 6992 KB Output is correct
8 Correct 762 ms 19280 KB Output is correct
9 Correct 722 ms 19028 KB Output is correct
10 Correct 39 ms 6992 KB Output is correct
11 Correct 684 ms 29552 KB Output is correct
12 Correct 598 ms 29476 KB Output is correct
13 Correct 305 ms 29440 KB Output is correct
14 Correct 39 ms 6988 KB Output is correct
15 Correct 400 ms 18008 KB Output is correct
16 Correct 708 ms 18224 KB Output is correct
17 Correct 583 ms 19076 KB Output is correct
18 Correct 670 ms 19152 KB Output is correct
19 Correct 631 ms 22356 KB Output is correct
20 Correct 580 ms 21412 KB Output is correct
21 Correct 669 ms 19028 KB Output is correct
22 Correct 677 ms 19024 KB Output is correct
23 Correct 774 ms 19536 KB Output is correct
24 Correct 757 ms 19560 KB Output is correct
25 Correct 939 ms 21840 KB Output is correct
26 Correct 620 ms 18328 KB Output is correct
27 Correct 597 ms 18420 KB Output is correct
28 Correct 39 ms 7004 KB Output is correct
29 Correct 78 ms 7504 KB Output is correct
30 Correct 65 ms 7508 KB Output is correct
31 Correct 72 ms 7764 KB Output is correct
32 Correct 48 ms 7820 KB Output is correct
33 Correct 74 ms 7508 KB Output is correct
34 Correct 39 ms 6992 KB Output is correct
35 Correct 913 ms 19516 KB Output is correct
36 Correct 1089 ms 19744 KB Output is correct
37 Correct 1387 ms 19596 KB Output is correct
38 Correct 42 ms 6996 KB Output is correct
39 Correct 663 ms 29700 KB Output is correct
40 Correct 337 ms 29908 KB Output is correct
41 Correct 675 ms 29520 KB Output is correct
42 Correct 723 ms 29620 KB Output is correct
43 Correct 37 ms 7004 KB Output is correct
44 Correct 568 ms 18512 KB Output is correct
45 Correct 1036 ms 18156 KB Output is correct
46 Correct 656 ms 18988 KB Output is correct
47 Correct 989 ms 19428 KB Output is correct
48 Correct 774 ms 21620 KB Output is correct
49 Correct 756 ms 23116 KB Output is correct
50 Correct 735 ms 22864 KB Output is correct
51 Correct 1107 ms 19724 KB Output is correct
52 Correct 1390 ms 19880 KB Output is correct
53 Correct 1509 ms 19692 KB Output is correct
54 Correct 1120 ms 19812 KB Output is correct
55 Correct 1380 ms 19900 KB Output is correct
56 Correct 1096 ms 19884 KB Output is correct
57 Correct 1134 ms 21812 KB Output is correct
58 Correct 987 ms 18916 KB Output is correct
59 Correct 608 ms 18312 KB Output is correct