oj.uz

Submission #1042401

# Submission time Handle Problem Language Result Execution time Memory
1042401 2024-08-03T03:47:17 Z sleepntsheep Inside information (BOI21_servers) C
50 / 100
 3500 ms 26272 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 700

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[2];
    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[0] != '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) {
        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] = 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[0] == 'S')
            ++j;
        else if (qq[i].type[0] == 'Q')
            printf(query_yesno(qq[i].b, qq[i].a, j - 1) ? "yes\n": "no\n");
        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 &&
                            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(" %s%d", s, &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 25 ms 2140 KB Output is correct
2 Correct 67 ms 2604 KB Output is correct
3 Correct 33 ms 2652 KB Output is correct
4 Correct 81 ms 2624 KB Output is correct
5 Correct 85 ms 2896 KB Output is correct
6 Correct 58 ms 3368 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2140 KB Output is correct
2 Correct 67 ms 2604 KB Output is correct
3 Correct 33 ms 2652 KB Output is correct
4 Correct 81 ms 2624 KB Output is correct
5 Correct 85 ms 2896 KB Output is correct
6 Correct 58 ms 3368 KB Output is correct
7 Correct 27 ms 2140 KB Output is correct
8 Incorrect 115 ms 2656 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 45 ms 2132 KB Output is correct
2 Correct 521 ms 17744 KB Output is correct
3 Correct 461 ms 17728 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 2132 KB Output is correct
2 Correct 521 ms 17744 KB Output is correct
3 Correct 461 ms 17728 KB Output is correct
4 Correct 43 ms 2132 KB Output is correct
5 Incorrect 530 ms 18076 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 32 ms 2644 KB Output is correct
2 Correct 885 ms 26108 KB Output is correct
3 Correct 885 ms 25976 KB Output is correct
4 Correct 380 ms 25940 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2644 KB Output is correct
2 Correct 885 ms 26108 KB Output is correct
3 Correct 885 ms 25976 KB Output is correct
4 Correct 380 ms 25940 KB Output is correct
5 Correct 33 ms 2236 KB Output is correct
6 Execution timed out 3560 ms 26116 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2140 KB Output is correct
2 Correct 333 ms 16764 KB Output is correct
3 Correct 1281 ms 16680 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2140 KB Output is correct
2 Correct 333 ms 16764 KB Output is correct
3 Correct 1281 ms 16680 KB Output is correct
4 Correct 23 ms 2756 KB Output is correct
5 Incorrect 614 ms 16968 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 23 ms 2140 KB Output is correct
2 Correct 1245 ms 26156 KB Output is correct
3 Correct 1022 ms 26096 KB Output is correct
4 Correct 414 ms 26204 KB Output is correct
5 Correct 21 ms 2652 KB Output is correct
6 Correct 317 ms 16612 KB Output is correct
7 Correct 1183 ms 16724 KB Output is correct
8 Correct 1417 ms 17692 KB Output is correct
9 Correct 1097 ms 17748 KB Output is correct
10 Correct 1120 ms 20096 KB Output is correct
11 Correct 1338 ms 19496 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2140 KB Output is correct
2 Correct 1245 ms 26156 KB Output is correct
3 Correct 1022 ms 26096 KB Output is correct
4 Correct 414 ms 26204 KB Output is correct
5 Correct 21 ms 2652 KB Output is correct
6 Correct 317 ms 16612 KB Output is correct
7 Correct 1183 ms 16724 KB Output is correct
8 Correct 1417 ms 17692 KB Output is correct
9 Correct 1097 ms 17748 KB Output is correct
10 Correct 1120 ms 20096 KB Output is correct
11 Correct 1338 ms 19496 KB Output is correct
12 Correct 24 ms 2140 KB Output is correct
13 Execution timed out 3564 ms 26272 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2808 KB Output is correct
2 Correct 72 ms 3156 KB Output is correct
3 Correct 32 ms 2652 KB Output is correct
4 Correct 57 ms 2724 KB Output is correct
5 Correct 58 ms 2836 KB Output is correct
6 Correct 35 ms 2644 KB Output is correct
7 Correct 42 ms 2744 KB Output is correct
8 Correct 493 ms 17748 KB Output is correct
9 Correct 516 ms 17732 KB Output is correct
10 Correct 26 ms 2648 KB Output is correct
11 Correct 1039 ms 26020 KB Output is correct
12 Correct 997 ms 26204 KB Output is correct
13 Correct 402 ms 26108 KB Output is correct
14 Correct 21 ms 2648 KB Output is correct
15 Correct 337 ms 16720 KB Output is correct
16 Correct 1250 ms 16724 KB Output is correct
17 Correct 1314 ms 17700 KB Output is correct
18 Correct 1033 ms 17748 KB Output is correct
19 Correct 975 ms 20432 KB Output is correct
20 Correct 1162 ms 19496 KB Output is correct
21 Correct 452 ms 17588 KB Output is correct
22 Correct 516 ms 17768 KB Output is correct
23 Correct 555 ms 18008 KB Output is correct
24 Correct 557 ms 18144 KB Output is correct
25 Correct 904 ms 20100 KB Output is correct
26 Correct 1357 ms 17028 KB Output is correct
27 Correct 1327 ms 16888 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2808 KB Output is correct
2 Correct 72 ms 3156 KB Output is correct
3 Correct 32 ms 2652 KB Output is correct
4 Correct 57 ms 2724 KB Output is correct
5 Correct 58 ms 2836 KB Output is correct
6 Correct 35 ms 2644 KB Output is correct
7 Correct 42 ms 2744 KB Output is correct
8 Correct 493 ms 17748 KB Output is correct
9 Correct 516 ms 17732 KB Output is correct
10 Correct 26 ms 2648 KB Output is correct
11 Correct 1039 ms 26020 KB Output is correct
12 Correct 997 ms 26204 KB Output is correct
13 Correct 402 ms 26108 KB Output is correct
14 Correct 21 ms 2648 KB Output is correct
15 Correct 337 ms 16720 KB Output is correct
16 Correct 1250 ms 16724 KB Output is correct
17 Correct 1314 ms 17700 KB Output is correct
18 Correct 1033 ms 17748 KB Output is correct
19 Correct 975 ms 20432 KB Output is correct
20 Correct 1162 ms 19496 KB Output is correct
21 Correct 452 ms 17588 KB Output is correct
22 Correct 516 ms 17768 KB Output is correct
23 Correct 555 ms 18008 KB Output is correct
24 Correct 557 ms 18144 KB Output is correct
25 Correct 904 ms 20100 KB Output is correct
26 Correct 1357 ms 17028 KB Output is correct
27 Correct 1327 ms 16888 KB Output is correct
28 Correct 23 ms 2648 KB Output is correct
29 Incorrect 90 ms 2480 KB Extra information in the output file
30 Halted 0 ms 0 KB -