oj.uz

Submission #1042391

# Submission time Handle Problem Language Result Execution time Memory
1042391 2024-08-03T03:32:05 Z sleepntsheep Inside information (BOI21_servers) C
50 / 100
 2848 ms 27732 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 1200010
#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;
    int ans;
} 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:131:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |     scanf("%d%d", &n, &q);
      |     ^~~~~~~~~~~~~~~~~~~~~
servers.c:138:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |         scanf(" %c%d", &c, &a);
      |         ^~~~~~~~~~~~~~~~~~~~~~
servers.c:140:13: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |             scanf("%d", &b);
      |             ^~~~~~~~~~~~~~~
servers.c:144:13: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |             scanf("%d", &b);
      |             ^~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2640 KB Output is correct
2 Correct 60 ms 3144 KB Output is correct
3 Correct 48 ms 3152 KB Output is correct
4 Correct 79 ms 3152 KB Output is correct
5 Correct 79 ms 3408 KB Output is correct
6 Correct 43 ms 3160 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2640 KB Output is correct
2 Correct 60 ms 3144 KB Output is correct
3 Correct 48 ms 3152 KB Output is correct
4 Correct 79 ms 3152 KB Output is correct
5 Correct 79 ms 3408 KB Output is correct
6 Correct 43 ms 3160 KB Output is correct
7 Incorrect 28 ms 2652 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 28 ms 2652 KB Output is correct
2 Correct 927 ms 19164 KB Output is correct
3 Correct 956 ms 19280 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2652 KB Output is correct
2 Correct 927 ms 19164 KB Output is correct
3 Correct 956 ms 19280 KB Output is correct
4 Incorrect 28 ms 2644 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 31 ms 2548 KB Output is correct
2 Correct 1720 ms 27564 KB Output is correct
3 Correct 1711 ms 27476 KB Output is correct
4 Correct 747 ms 27620 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2548 KB Output is correct
2 Correct 1720 ms 27564 KB Output is correct
3 Correct 1711 ms 27476 KB Output is correct
4 Correct 747 ms 27620 KB Output is correct
5 Incorrect 29 ms 2644 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 28 ms 2648 KB Output is correct
2 Correct 634 ms 18244 KB Output is correct
3 Correct 1852 ms 18120 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2648 KB Output is correct
2 Correct 634 ms 18244 KB Output is correct
3 Correct 1852 ms 18120 KB Output is correct
4 Incorrect 28 ms 2648 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 31 ms 2716 KB Output is correct
2 Correct 1705 ms 27700 KB Output is correct
3 Correct 1673 ms 27732 KB Output is correct
4 Correct 732 ms 27472 KB Output is correct
5 Correct 30 ms 2648 KB Output is correct
6 Correct 638 ms 18220 KB Output is correct
7 Correct 1940 ms 18256 KB Output is correct
8 Correct 2278 ms 19228 KB Output is correct
9 Correct 1938 ms 19384 KB Output is correct
10 Correct 1880 ms 21584 KB Output is correct
11 Correct 2277 ms 21068 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2716 KB Output is correct
2 Correct 1705 ms 27700 KB Output is correct
3 Correct 1673 ms 27732 KB Output is correct
4 Correct 732 ms 27472 KB Output is correct
5 Correct 30 ms 2648 KB Output is correct
6 Correct 638 ms 18220 KB Output is correct
7 Correct 1940 ms 18256 KB Output is correct
8 Correct 2278 ms 19228 KB Output is correct
9 Correct 1938 ms 19384 KB Output is correct
10 Correct 1880 ms 21584 KB Output is correct
11 Correct 2277 ms 21068 KB Output is correct
12 Incorrect 29 ms 2640 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 32 ms 2640 KB Output is correct
2 Correct 61 ms 3092 KB Output is correct
3 Correct 52 ms 3160 KB Output is correct
4 Correct 80 ms 3196 KB Output is correct
5 Correct 79 ms 3408 KB Output is correct
6 Correct 41 ms 3336 KB Output is correct
7 Correct 28 ms 2640 KB Output is correct
8 Correct 898 ms 19024 KB Output is correct
9 Correct 919 ms 19276 KB Output is correct
10 Correct 29 ms 2744 KB Output is correct
11 Correct 1704 ms 27536 KB Output is correct
12 Correct 1659 ms 27684 KB Output is correct
13 Correct 719 ms 27552 KB Output is correct
14 Correct 29 ms 2652 KB Output is correct
15 Correct 636 ms 18252 KB Output is correct
16 Correct 1862 ms 18136 KB Output is correct
17 Correct 2287 ms 19056 KB Output is correct
18 Correct 1921 ms 19284 KB Output is correct
19 Correct 1897 ms 21588 KB Output is correct
20 Correct 2228 ms 21096 KB Output is correct
21 Correct 949 ms 19292 KB Output is correct
22 Correct 1006 ms 19284 KB Output is correct
23 Correct 1193 ms 19792 KB Output is correct
24 Correct 1289 ms 19796 KB Output is correct
25 Correct 1845 ms 21416 KB Output is correct
26 Correct 2799 ms 18512 KB Output is correct
27 Correct 2848 ms 18404 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2640 KB Output is correct
2 Correct 61 ms 3092 KB Output is correct
3 Correct 52 ms 3160 KB Output is correct
4 Correct 80 ms 3196 KB Output is correct
5 Correct 79 ms 3408 KB Output is correct
6 Correct 41 ms 3336 KB Output is correct
7 Correct 28 ms 2640 KB Output is correct
8 Correct 898 ms 19024 KB Output is correct
9 Correct 919 ms 19276 KB Output is correct
10 Correct 29 ms 2744 KB Output is correct
11 Correct 1704 ms 27536 KB Output is correct
12 Correct 1659 ms 27684 KB Output is correct
13 Correct 719 ms 27552 KB Output is correct
14 Correct 29 ms 2652 KB Output is correct
15 Correct 636 ms 18252 KB Output is correct
16 Correct 1862 ms 18136 KB Output is correct
17 Correct 2287 ms 19056 KB Output is correct
18 Correct 1921 ms 19284 KB Output is correct
19 Correct 1897 ms 21588 KB Output is correct
20 Correct 2228 ms 21096 KB Output is correct
21 Correct 949 ms 19292 KB Output is correct
22 Correct 1006 ms 19284 KB Output is correct
23 Correct 1193 ms 19792 KB Output is correct
24 Correct 1289 ms 19796 KB Output is correct
25 Correct 1845 ms 21416 KB Output is correct
26 Correct 2799 ms 18512 KB Output is correct
27 Correct 2848 ms 18404 KB Output is correct
28 Incorrect 36 ms 2548 KB Extra information in the output file
29 Halted 0 ms 0 KB -