oj.uz

Submission #1042393

# Submission time Handle Problem Language Result Execution time Memory
1042393 2024-08-03T03:35:51 Z sleepntsheep Inside information (BOI21_servers) C
50 / 100
 3223 ms 26660 KB 
#include <stdio.h>
#include <stdlib.h>

/*
 * 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)
 */

#define N 120001
#define B 300

int n, q, pp[N], jj[N], dd[N], up[N], temp, inc[N], map_time[N];

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) {
    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;
        jj[v] = (dd[u] - dd[jj[u]] == dd[jj[u]] - dd[jj[jj[u]]]) ? jj[jj[u]]: u;

        up[v] = fh[u][j];
        dfs(v, u);
    }
}

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

int anc(int u, int dep) {
    while (dd[u] > dep)
        u = (dd[jj[u]] >= dep) ? jj[u] : pp[u];
    return u;
}

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

/* 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 = anc(v, dd[a] + 1);
        return inc[v] - inc[va] == dd[v] - dd[va] && up[v] <= time;
    }
    if (v == a) {
        ua = anc(u, dd[a] + 1);
        return inc[u] - inc[ua] == 0 && up[ua] <= time;
    }
    ua = anc(u, dd[a] + 1);
    va = anc(v, dd[a] + 1);

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

int dp[N], comp[N];

void efs(int u, int p, int time, int root) {
    comp[u] = root;
    for (int j = 0; j < eo[u]; ++j)
        if (eh[u][j] != p && fh[u][j] <= time && comp[eh[u][j]] == -1)
            efs(eh[u][j], u, time, root);
}

void build(int ii, int tme) {
    for (int i = 1; i <= n; ++i)
        dp[i] = 1, comp[i] = -1;

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

        int x = dp[qq[i].a], y = dp[qq[i].b];
        dp[qq[i].a] += y;
        dp[qq[i].b] += x;
    }

    for (int i = 1; i <= n; ++i)
        if (comp[i] == -1)
            efs(i, i, tme, i);
}

int counted[N];

int main() {
    scanf("%d%d", &n, &q);

    q = n + q - 1;
    for (int j = 0, i = 0; i < q; ++i) {
        char c;
        int a, b = 0;

        scanf(" %c%d", &c, &a);
        if (c == 'S') {
            scanf("%d", &b);
            link(a, b, j++);
            map_time[j - 1] = i;
        } else if (c == 'Q')
            scanf("%d", &b);

        qq[i] = (struct Query){c, a, b};
    }

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

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

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

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

        if (i % B == 0) {
            build(i, j);
            at = i + 1;
        }
    }
}

Compilation message

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

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2040 KB Output is correct
2 Correct 69 ms 2700 KB Output is correct
3 Correct 57 ms 2764 KB Output is correct
4 Correct 91 ms 2600 KB Output is correct
5 Correct 87 ms 2900 KB Output is correct
6 Correct 47 ms 2632 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2040 KB Output is correct
2 Correct 69 ms 2700 KB Output is correct
3 Correct 57 ms 2764 KB Output is correct
4 Correct 91 ms 2600 KB Output is correct
5 Correct 87 ms 2900 KB Output is correct
6 Correct 47 ms 2632 KB Output is correct
7 Incorrect 34 ms 2140 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2132 KB Output is correct
2 Correct 1041 ms 18008 KB Output is correct
3 Correct 1018 ms 18196 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2132 KB Output is correct
2 Correct 1041 ms 18008 KB Output is correct
3 Correct 1018 ms 18196 KB Output is correct
4 Incorrect 42 ms 2128 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 2108 KB Output is correct
2 Correct 1694 ms 26448 KB Output is correct
3 Correct 1779 ms 26472 KB Output is correct
4 Correct 722 ms 26580 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 2108 KB Output is correct
2 Correct 1694 ms 26448 KB Output is correct
3 Correct 1779 ms 26472 KB Output is correct
4 Correct 722 ms 26580 KB Output is correct
5 Incorrect 35 ms 2140 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 2140 KB Output is correct
2 Correct 635 ms 17236 KB Output is correct
3 Correct 1884 ms 17232 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 2140 KB Output is correct
2 Correct 635 ms 17236 KB Output is correct
3 Correct 1884 ms 17232 KB Output is correct
4 Incorrect 35 ms 2136 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2128 KB Output is correct
2 Correct 1748 ms 26656 KB Output is correct
3 Correct 1747 ms 26508 KB Output is correct
4 Correct 724 ms 26640 KB Output is correct
5 Correct 41 ms 2132 KB Output is correct
6 Correct 643 ms 17152 KB Output is correct
7 Correct 1852 ms 17236 KB Output is correct
8 Correct 2313 ms 18152 KB Output is correct
9 Correct 1911 ms 18164 KB Output is correct
10 Correct 1926 ms 20560 KB Output is correct
11 Correct 2285 ms 20052 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2128 KB Output is correct
2 Correct 1748 ms 26656 KB Output is correct
3 Correct 1747 ms 26508 KB Output is correct
4 Correct 724 ms 26640 KB Output is correct
5 Correct 41 ms 2132 KB Output is correct
6 Correct 643 ms 17152 KB Output is correct
7 Correct 1852 ms 17236 KB Output is correct
8 Correct 2313 ms 18152 KB Output is correct
9 Correct 1911 ms 18164 KB Output is correct
10 Correct 1926 ms 20560 KB Output is correct
11 Correct 2285 ms 20052 KB Output is correct
12 Incorrect 36 ms 2140 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2132 KB Output is correct
2 Correct 79 ms 2644 KB Output is correct
3 Correct 59 ms 2644 KB Output is correct
4 Correct 82 ms 2680 KB Output is correct
5 Correct 87 ms 2900 KB Output is correct
6 Correct 48 ms 2644 KB Output is correct
7 Correct 34 ms 2140 KB Output is correct
8 Correct 940 ms 18016 KB Output is correct
9 Correct 927 ms 18260 KB Output is correct
10 Correct 36 ms 2132 KB Output is correct
11 Correct 1732 ms 26660 KB Output is correct
12 Correct 1687 ms 26620 KB Output is correct
13 Correct 742 ms 26448 KB Output is correct
14 Correct 42 ms 2136 KB Output is correct
15 Correct 647 ms 17240 KB Output is correct
16 Correct 1847 ms 17236 KB Output is correct
17 Correct 2244 ms 18004 KB Output is correct
18 Correct 1892 ms 18224 KB Output is correct
19 Correct 1919 ms 20660 KB Output is correct
20 Correct 2319 ms 20020 KB Output is correct
21 Correct 933 ms 18220 KB Output is correct
22 Correct 1059 ms 18044 KB Output is correct
23 Correct 1280 ms 18520 KB Output is correct
24 Correct 1293 ms 18568 KB Output is correct
25 Correct 1992 ms 20340 KB Output is correct
26 Correct 3166 ms 17500 KB Output is correct
27 Correct 3223 ms 17480 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2132 KB Output is correct
2 Correct 79 ms 2644 KB Output is correct
3 Correct 59 ms 2644 KB Output is correct
4 Correct 82 ms 2680 KB Output is correct
5 Correct 87 ms 2900 KB Output is correct
6 Correct 48 ms 2644 KB Output is correct
7 Correct 34 ms 2140 KB Output is correct
8 Correct 940 ms 18016 KB Output is correct
9 Correct 927 ms 18260 KB Output is correct
10 Correct 36 ms 2132 KB Output is correct
11 Correct 1732 ms 26660 KB Output is correct
12 Correct 1687 ms 26620 KB Output is correct
13 Correct 742 ms 26448 KB Output is correct
14 Correct 42 ms 2136 KB Output is correct
15 Correct 647 ms 17240 KB Output is correct
16 Correct 1847 ms 17236 KB Output is correct
17 Correct 2244 ms 18004 KB Output is correct
18 Correct 1892 ms 18224 KB Output is correct
19 Correct 1919 ms 20660 KB Output is correct
20 Correct 2319 ms 20020 KB Output is correct
21 Correct 933 ms 18220 KB Output is correct
22 Correct 1059 ms 18044 KB Output is correct
23 Correct 1280 ms 18520 KB Output is correct
24 Correct 1293 ms 18568 KB Output is correct
25 Correct 1992 ms 20340 KB Output is correct
26 Correct 3166 ms 17500 KB Output is correct
27 Correct 3223 ms 17480 KB Output is correct
28 Incorrect 35 ms 2136 KB Extra information in the output file
29 Halted 0 ms 0 KB -