oj.uz

Submission #1042403

# Submission time Handle Problem Language Result Execution time Memory
1042403 2024-08-03T03:49:11 Z sleepntsheep Inside information (BOI21_servers) C
50 / 100
 3500 ms 26192 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);
        }

    }
}

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 16 ms 2652 KB Output is correct
2 Correct 34 ms 3260 KB Output is correct
3 Correct 20 ms 2652 KB Output is correct
4 Correct 38 ms 2640 KB Output is correct
5 Correct 37 ms 2908 KB Output is correct
6 Correct 18 ms 2652 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2652 KB Output is correct
2 Correct 34 ms 3260 KB Output is correct
3 Correct 20 ms 2652 KB Output is correct
4 Correct 38 ms 2640 KB Output is correct
5 Correct 37 ms 2908 KB Output is correct
6 Correct 18 ms 2652 KB Output is correct
7 Correct 231 ms 2132 KB Output is correct
8 Execution timed out 3562 ms 3236 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2756 KB Output is correct
2 Correct 49 ms 17604 KB Output is correct
3 Correct 48 ms 17756 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2756 KB Output is correct
2 Correct 49 ms 17604 KB Output is correct
3 Correct 48 ms 17756 KB Output is correct
4 Correct 221 ms 2904 KB Output is correct
5 Execution timed out 3570 ms 18088 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2652 KB Output is correct
2 Correct 60 ms 26168 KB Output is correct
3 Correct 69 ms 26192 KB Output is correct
4 Correct 83 ms 25944 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2652 KB Output is correct
2 Correct 60 ms 26168 KB Output is correct
3 Correct 69 ms 26192 KB Output is correct
4 Correct 83 ms 25944 KB Output is correct
5 Correct 240 ms 2648 KB Output is correct
6 Execution timed out 3537 ms 26044 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2652 KB Output is correct
2 Correct 54 ms 16620 KB Output is correct
3 Correct 63 ms 16724 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2652 KB Output is correct
2 Correct 54 ms 16620 KB Output is correct
3 Correct 63 ms 16724 KB Output is correct
4 Correct 243 ms 2188 KB Output is correct
5 Execution timed out 3568 ms 16408 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2648 KB Output is correct
2 Correct 61 ms 26064 KB Output is correct
3 Correct 59 ms 26192 KB Output is correct
4 Correct 82 ms 26076 KB Output is correct
5 Correct 17 ms 2136 KB Output is correct
6 Correct 59 ms 16672 KB Output is correct
7 Correct 65 ms 16648 KB Output is correct
8 Correct 92 ms 17748 KB Output is correct
9 Correct 69 ms 17792 KB Output is correct
10 Correct 70 ms 20048 KB Output is correct
11 Correct 115 ms 19488 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2648 KB Output is correct
2 Correct 61 ms 26064 KB Output is correct
3 Correct 59 ms 26192 KB Output is correct
4 Correct 82 ms 26076 KB Output is correct
5 Correct 17 ms 2136 KB Output is correct
6 Correct 59 ms 16672 KB Output is correct
7 Correct 65 ms 16648 KB Output is correct
8 Correct 92 ms 17748 KB Output is correct
9 Correct 69 ms 17792 KB Output is correct
10 Correct 70 ms 20048 KB Output is correct
11 Correct 115 ms 19488 KB Output is correct
12 Correct 223 ms 2652 KB Output is correct
13 Execution timed out 3583 ms 26092 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2652 KB Output is correct
2 Correct 23 ms 2712 KB Output is correct
3 Correct 19 ms 2708 KB Output is correct
4 Correct 38 ms 2624 KB Output is correct
5 Correct 37 ms 2908 KB Output is correct
6 Correct 18 ms 3416 KB Output is correct
7 Correct 15 ms 2156 KB Output is correct
8 Correct 48 ms 17700 KB Output is correct
9 Correct 48 ms 17648 KB Output is correct
10 Correct 16 ms 2648 KB Output is correct
11 Correct 60 ms 26192 KB Output is correct
12 Correct 60 ms 26192 KB Output is correct
13 Correct 103 ms 26116 KB Output is correct
14 Correct 16 ms 2652 KB Output is correct
15 Correct 52 ms 16520 KB Output is correct
16 Correct 69 ms 16720 KB Output is correct
17 Correct 94 ms 17552 KB Output is correct
18 Correct 60 ms 17660 KB Output is correct
19 Correct 70 ms 20052 KB Output is correct
20 Correct 108 ms 19368 KB Output is correct
21 Correct 52 ms 17492 KB Output is correct
22 Correct 51 ms 17528 KB Output is correct
23 Correct 56 ms 17924 KB Output is correct
24 Correct 54 ms 18004 KB Output is correct
25 Correct 59 ms 19764 KB Output is correct
26 Correct 61 ms 16980 KB Output is correct
27 Correct 55 ms 17020 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2652 KB Output is correct
2 Correct 23 ms 2712 KB Output is correct
3 Correct 19 ms 2708 KB Output is correct
4 Correct 38 ms 2624 KB Output is correct
5 Correct 37 ms 2908 KB Output is correct
6 Correct 18 ms 3416 KB Output is correct
7 Correct 15 ms 2156 KB Output is correct
8 Correct 48 ms 17700 KB Output is correct
9 Correct 48 ms 17648 KB Output is correct
10 Correct 16 ms 2648 KB Output is correct
11 Correct 60 ms 26192 KB Output is correct
12 Correct 60 ms 26192 KB Output is correct
13 Correct 103 ms 26116 KB Output is correct
14 Correct 16 ms 2652 KB Output is correct
15 Correct 52 ms 16520 KB Output is correct
16 Correct 69 ms 16720 KB Output is correct
17 Correct 94 ms 17552 KB Output is correct
18 Correct 60 ms 17660 KB Output is correct
19 Correct 70 ms 20052 KB Output is correct
20 Correct 108 ms 19368 KB Output is correct
21 Correct 52 ms 17492 KB Output is correct
22 Correct 51 ms 17528 KB Output is correct
23 Correct 56 ms 17924 KB Output is correct
24 Correct 54 ms 18004 KB Output is correct
25 Correct 59 ms 19764 KB Output is correct
26 Correct 61 ms 16980 KB Output is correct
27 Correct 55 ms 17020 KB Output is correct
28 Correct 217 ms 2848 KB Output is correct
29 Execution timed out 3558 ms 3240 KB Time limit exceeded
30 Halted 0 ms 0 KB -