oj.uz

Submission #1042411

# Submission time Handle Problem Language Result Execution time Memory
1042411 2024-08-03T04:03:06 Z sleepntsheep Inside information (BOI21_servers) C
32.5 / 100
 3500 ms 26356 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[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;
    ua = anc(u, dd[a] + 1);
    va = anc(v, dd[a] + 1);

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

    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;

        if (i % B == 0) {
            build(i, j);
            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') {

            build(i, j);
            printf("%d\n", dp[qq[i].a]);
            continue;
            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);
        }

    }
}

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:127:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |     scanf("%d%d", &n, &q);
      |     ^~~~~~~~~~~~~~~~~~~~~
servers.c:134:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |         scanf(" %s%d", s, &a);
      |         ^~~~~~~~~~~~~~~~~~~~~
servers.c:136:13: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |             scanf("%d", &b);
      |             ^~~~~~~~~~~~~~~
servers.c:139:13: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |             scanf("%d", &b);
      |             ^~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2648 KB Output is correct
2 Correct 59 ms 2520 KB Output is correct
3 Correct 48 ms 2668 KB Output is correct
4 Correct 80 ms 2900 KB Output is correct
5 Correct 84 ms 2900 KB Output is correct
6 Correct 42 ms 2644 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2648 KB Output is correct
2 Correct 59 ms 2520 KB Output is correct
3 Correct 48 ms 2668 KB Output is correct
4 Correct 80 ms 2900 KB Output is correct
5 Correct 84 ms 2900 KB Output is correct
6 Correct 42 ms 2644 KB Output is correct
7 Correct 443 ms 2276 KB Output is correct
8 Execution timed out 3549 ms 2604 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2900 KB Output is correct
2 Correct 911 ms 17688 KB Output is correct
3 Correct 909 ms 17744 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2900 KB Output is correct
2 Correct 911 ms 17688 KB Output is correct
3 Correct 909 ms 17744 KB Output is correct
4 Correct 407 ms 2132 KB Output is correct
5 Execution timed out 3521 ms 17332 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2652 KB Output is correct
2 Correct 1775 ms 26192 KB Output is correct
3 Correct 1758 ms 26192 KB Output is correct
4 Correct 717 ms 26004 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2652 KB Output is correct
2 Correct 1775 ms 26192 KB Output is correct
3 Correct 1758 ms 26192 KB Output is correct
4 Correct 717 ms 26004 KB Output is correct
5 Correct 433 ms 2748 KB Output is correct
6 Execution timed out 3544 ms 25940 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2136 KB Output is correct
2 Correct 620 ms 16556 KB Output is correct
3 Correct 1849 ms 16620 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2136 KB Output is correct
2 Correct 620 ms 16556 KB Output is correct
3 Correct 1849 ms 16620 KB Output is correct
4 Correct 418 ms 2384 KB Output is correct
5 Execution timed out 3577 ms 16212 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2160 KB Output is correct
2 Correct 1722 ms 26356 KB Output is correct
3 Correct 1726 ms 26100 KB Output is correct
4 Correct 737 ms 25940 KB Output is correct
5 Correct 30 ms 2652 KB Output is correct
6 Correct 631 ms 16636 KB Output is correct
7 Correct 1865 ms 16724 KB Output is correct
8 Correct 2395 ms 17752 KB Output is correct
9 Correct 1981 ms 17780 KB Output is correct
10 Correct 1814 ms 20308 KB Output is correct
11 Correct 2266 ms 19588 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2160 KB Output is correct
2 Correct 1722 ms 26356 KB Output is correct
3 Correct 1726 ms 26100 KB Output is correct
4 Correct 737 ms 25940 KB Output is correct
5 Correct 30 ms 2652 KB Output is correct
6 Correct 631 ms 16636 KB Output is correct
7 Correct 1865 ms 16724 KB Output is correct
8 Correct 2395 ms 17752 KB Output is correct
9 Correct 1981 ms 17780 KB Output is correct
10 Correct 1814 ms 20308 KB Output is correct
11 Correct 2266 ms 19588 KB Output is correct
12 Correct 443 ms 2228 KB Output is correct
13 Execution timed out 3555 ms 25712 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2132 KB Output is correct
2 Correct 60 ms 2688 KB Output is correct
3 Correct 54 ms 2792 KB Output is correct
4 Correct 76 ms 2708 KB Output is correct
5 Correct 80 ms 2860 KB Output is correct
6 Correct 43 ms 2652 KB Output is correct
7 Correct 33 ms 2764 KB Output is correct
8 Correct 943 ms 17748 KB Output is correct
9 Correct 943 ms 17752 KB Output is correct
10 Correct 32 ms 2136 KB Output is correct
11 Correct 1950 ms 26196 KB Output is correct
12 Correct 2374 ms 26196 KB Output is correct
13 Correct 787 ms 25968 KB Output is correct
14 Correct 30 ms 2160 KB Output is correct
15 Correct 660 ms 16536 KB Output is correct
16 Correct 2184 ms 16724 KB Output is correct
17 Correct 2991 ms 17748 KB Output is correct
18 Correct 2353 ms 17700 KB Output is correct
19 Correct 1978 ms 20052 KB Output is correct
20 Correct 2567 ms 19588 KB Output is correct
21 Correct 1082 ms 17684 KB Output is correct
22 Correct 1105 ms 17744 KB Output is correct
23 Correct 1850 ms 18000 KB Output is correct
24 Correct 1393 ms 18056 KB Output is correct
25 Correct 2132 ms 19936 KB Output is correct
26 Execution timed out 3560 ms 16888 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2132 KB Output is correct
2 Correct 60 ms 2688 KB Output is correct
3 Correct 54 ms 2792 KB Output is correct
4 Correct 76 ms 2708 KB Output is correct
5 Correct 80 ms 2860 KB Output is correct
6 Correct 43 ms 2652 KB Output is correct
7 Correct 33 ms 2764 KB Output is correct
8 Correct 943 ms 17748 KB Output is correct
9 Correct 943 ms 17752 KB Output is correct
10 Correct 32 ms 2136 KB Output is correct
11 Correct 1950 ms 26196 KB Output is correct
12 Correct 2374 ms 26196 KB Output is correct
13 Correct 787 ms 25968 KB Output is correct
14 Correct 30 ms 2160 KB Output is correct
15 Correct 660 ms 16536 KB Output is correct
16 Correct 2184 ms 16724 KB Output is correct
17 Correct 2991 ms 17748 KB Output is correct
18 Correct 2353 ms 17700 KB Output is correct
19 Correct 1978 ms 20052 KB Output is correct
20 Correct 2567 ms 19588 KB Output is correct
21 Correct 1082 ms 17684 KB Output is correct
22 Correct 1105 ms 17744 KB Output is correct
23 Correct 1850 ms 18000 KB Output is correct
24 Correct 1393 ms 18056 KB Output is correct
25 Correct 2132 ms 19936 KB Output is correct
26 Execution timed out 3560 ms 16888 KB Time limit exceeded
27 Halted 0 ms 0 KB -