oj.uz

Submission #1042396

# Submission time Handle Problem Language Result Execution time Memory
1042396 2024-08-03T03:42:17 Z sleepntsheep Inside information (BOI21_servers) C
50 / 100
 3371 ms 26452 KB 
/* WHAT IS EXTRA INFORAMZTION GTR RR */

#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];

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 time, int root) {
    comp[u] = root;
    for (int j = 0; j < eo[u]; ++j)
        if (fh[u][j] <= time && comp[eh[u][j]] == -1)
            efs(eh[u][j], 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, 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++);
        } 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 == 'C') {
            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:142:13: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |             scanf("%d", &b);
      |             ^~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2652 KB Output is correct
2 Correct 65 ms 3276 KB Output is correct
3 Correct 53 ms 2732 KB Output is correct
4 Correct 81 ms 2716 KB Output is correct
5 Correct 85 ms 2900 KB Output is correct
6 Correct 48 ms 2644 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2652 KB Output is correct
2 Correct 65 ms 3276 KB Output is correct
3 Correct 53 ms 2732 KB Output is correct
4 Correct 81 ms 2716 KB Output is correct
5 Correct 85 ms 2900 KB Output is correct
6 Correct 48 ms 2644 KB Output is correct
7 Correct 43 ms 2140 KB Output is correct
8 Incorrect 89 ms 2640 KB Extra information in the output file
9 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2896 KB Output is correct
2 Correct 980 ms 17704 KB Output is correct
3 Correct 940 ms 17748 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2896 KB Output is correct
2 Correct 980 ms 17704 KB Output is correct
3 Correct 940 ms 17748 KB Output is correct
4 Correct 34 ms 2140 KB Output is correct
5 Incorrect 996 ms 18168 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2040 KB Output is correct
2 Correct 1675 ms 26008 KB Output is correct
3 Correct 1751 ms 26120 KB Output is correct
4 Correct 728 ms 26132 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2040 KB Output is correct
2 Correct 1675 ms 26008 KB Output is correct
3 Correct 1751 ms 26120 KB Output is correct
4 Correct 728 ms 26132 KB Output is correct
5 Correct 36 ms 2652 KB Output is correct
6 Incorrect 3371 ms 26268 KB Extra information in the output file
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2140 KB Output is correct
2 Correct 641 ms 16696 KB Output is correct
3 Correct 1922 ms 16764 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2140 KB Output is correct
2 Correct 641 ms 16696 KB Output is correct
3 Correct 1922 ms 16764 KB Output is correct
4 Correct 35 ms 2652 KB Output is correct
5 Incorrect 728 ms 16948 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 2828 KB Output is correct
2 Correct 1739 ms 26212 KB Output is correct
3 Correct 1853 ms 26168 KB Output is correct
4 Correct 708 ms 25940 KB Output is correct
5 Correct 34 ms 2828 KB Output is correct
6 Correct 635 ms 16716 KB Output is correct
7 Correct 1965 ms 16756 KB Output is correct
8 Correct 2277 ms 17700 KB Output is correct
9 Correct 1827 ms 17720 KB Output is correct
10 Correct 1736 ms 20196 KB Output is correct
11 Correct 2074 ms 19376 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 2828 KB Output is correct
2 Correct 1739 ms 26212 KB Output is correct
3 Correct 1853 ms 26168 KB Output is correct
4 Correct 708 ms 25940 KB Output is correct
5 Correct 34 ms 2828 KB Output is correct
6 Correct 635 ms 16716 KB Output is correct
7 Correct 1965 ms 16756 KB Output is correct
8 Correct 2277 ms 17700 KB Output is correct
9 Correct 1827 ms 17720 KB Output is correct
10 Correct 1736 ms 20196 KB Output is correct
11 Correct 2074 ms 19376 KB Output is correct
12 Correct 36 ms 2652 KB Output is correct
13 Incorrect 3366 ms 26216 KB Extra information in the output file
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2652 KB Output is correct
2 Correct 73 ms 3156 KB Output is correct
3 Correct 53 ms 2736 KB Output is correct
4 Correct 84 ms 2640 KB Output is correct
5 Correct 84 ms 2968 KB Output is correct
6 Correct 48 ms 2676 KB Output is correct
7 Correct 34 ms 2128 KB Output is correct
8 Correct 1002 ms 17616 KB Output is correct
9 Correct 1006 ms 18008 KB Output is correct
10 Correct 35 ms 2136 KB Output is correct
11 Correct 1702 ms 26136 KB Output is correct
12 Correct 1724 ms 26452 KB Output is correct
13 Correct 743 ms 25968 KB Output is correct
14 Correct 37 ms 2140 KB Output is correct
15 Correct 629 ms 16720 KB Output is correct
16 Correct 1895 ms 16824 KB Output is correct
17 Correct 2406 ms 17708 KB Output is correct
18 Correct 1874 ms 17744 KB Output is correct
19 Correct 1743 ms 20212 KB Output is correct
20 Correct 2092 ms 19796 KB Output is correct
21 Correct 937 ms 17732 KB Output is correct
22 Correct 981 ms 17724 KB Output is correct
23 Correct 1170 ms 18116 KB Output is correct
24 Correct 1113 ms 18000 KB Output is correct
25 Correct 1852 ms 19900 KB Output is correct
26 Correct 2920 ms 16976 KB Output is correct
27 Correct 2908 ms 16888 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2652 KB Output is correct
2 Correct 73 ms 3156 KB Output is correct
3 Correct 53 ms 2736 KB Output is correct
4 Correct 84 ms 2640 KB Output is correct
5 Correct 84 ms 2968 KB Output is correct
6 Correct 48 ms 2676 KB Output is correct
7 Correct 34 ms 2128 KB Output is correct
8 Correct 1002 ms 17616 KB Output is correct
9 Correct 1006 ms 18008 KB Output is correct
10 Correct 35 ms 2136 KB Output is correct
11 Correct 1702 ms 26136 KB Output is correct
12 Correct 1724 ms 26452 KB Output is correct
13 Correct 743 ms 25968 KB Output is correct
14 Correct 37 ms 2140 KB Output is correct
15 Correct 629 ms 16720 KB Output is correct
16 Correct 1895 ms 16824 KB Output is correct
17 Correct 2406 ms 17708 KB Output is correct
18 Correct 1874 ms 17744 KB Output is correct
19 Correct 1743 ms 20212 KB Output is correct
20 Correct 2092 ms 19796 KB Output is correct
21 Correct 937 ms 17732 KB Output is correct
22 Correct 981 ms 17724 KB Output is correct
23 Correct 1170 ms 18116 KB Output is correct
24 Correct 1113 ms 18000 KB Output is correct
25 Correct 1852 ms 19900 KB Output is correct
26 Correct 2920 ms 16976 KB Output is correct
27 Correct 2908 ms 16888 KB Output is correct
28 Correct 48 ms 2648 KB Output is correct
29 Incorrect 88 ms 3156 KB Extra information in the output file
30 Halted 0 ms 0 KB -