oj.uz

Submission #1042383

# Submission time Handle Problem Language Result Execution time Memory
1042383 2024-08-03T03:18:27 Z sleepntsheep Inside information (BOI21_servers) C
50 / 100
 3500 ms 31060 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)
 */

#define N 120001
#define B 400


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 = anc(v, dd[a] + 1);
    int ua = anc(u, 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 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;
        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 {
            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:28:26: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   28 |     else if (0 == (o & o - 1)) eh[i] = (int*)realloc(eh[i], 2 * o * sizeof **eh);
      |                        ~~^~~
servers.c: In function 'main':
servers.c:125:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |     scanf("%d%d", &n, &q);
      |     ^~~~~~~~~~~~~~~~~~~~~
servers.c:131:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |         scanf(" %c%d", &c, &a);
      |         ^~~~~~~~~~~~~~~~~~~~~~
servers.c:133:13: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |             scanf("%d", &b);
      |             ^~~~~~~~~~~~~~~
servers.c:137:13: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |             scanf("%d", &b);
      |             ^~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3416 KB Output is correct
2 Correct 58 ms 4432 KB Output is correct
3 Correct 47 ms 4688 KB Output is correct
4 Correct 76 ms 4688 KB Output is correct
5 Correct 75 ms 4692 KB Output is correct
6 Correct 55 ms 4816 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3416 KB Output is correct
2 Correct 58 ms 4432 KB Output is correct
3 Correct 47 ms 4688 KB Output is correct
4 Correct 76 ms 4688 KB Output is correct
5 Correct 75 ms 4692 KB Output is correct
6 Correct 55 ms 4816 KB Output is correct
7 Correct 34 ms 3416 KB Output is correct
8 Incorrect 88 ms 4180 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 30 ms 3416 KB Output is correct
2 Correct 713 ms 21772 KB Output is correct
3 Correct 718 ms 21840 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3416 KB Output is correct
2 Correct 713 ms 21772 KB Output is correct
3 Correct 718 ms 21840 KB Output is correct
4 Correct 31 ms 3416 KB Output is correct
5 Incorrect 760 ms 22356 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 3412 KB Output is correct
2 Correct 1399 ms 30896 KB Output is correct
3 Correct 1331 ms 30800 KB Output is correct
4 Correct 615 ms 31060 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 3412 KB Output is correct
2 Correct 1399 ms 30896 KB Output is correct
3 Correct 1331 ms 30800 KB Output is correct
4 Correct 615 ms 31060 KB Output is correct
5 Correct 32 ms 3452 KB Output is correct
6 Execution timed out 3516 ms 30600 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3408 KB Output is correct
2 Correct 504 ms 21320 KB Output is correct
3 Correct 1452 ms 21488 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3408 KB Output is correct
2 Correct 504 ms 21320 KB Output is correct
3 Correct 1452 ms 21488 KB Output is correct
4 Correct 31 ms 3416 KB Output is correct
5 Incorrect 650 ms 21472 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 32 ms 3420 KB Output is correct
2 Correct 1369 ms 30900 KB Output is correct
3 Correct 1453 ms 30920 KB Output is correct
4 Correct 613 ms 30804 KB Output is correct
5 Correct 31 ms 3396 KB Output is correct
6 Correct 491 ms 21324 KB Output is correct
7 Correct 1508 ms 21580 KB Output is correct
8 Correct 1799 ms 22420 KB Output is correct
9 Correct 1524 ms 22356 KB Output is correct
10 Correct 1473 ms 24916 KB Output is correct
11 Correct 1835 ms 24256 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3420 KB Output is correct
2 Correct 1369 ms 30900 KB Output is correct
3 Correct 1453 ms 30920 KB Output is correct
4 Correct 613 ms 30804 KB Output is correct
5 Correct 31 ms 3396 KB Output is correct
6 Correct 491 ms 21324 KB Output is correct
7 Correct 1508 ms 21580 KB Output is correct
8 Correct 1799 ms 22420 KB Output is correct
9 Correct 1524 ms 22356 KB Output is correct
10 Correct 1473 ms 24916 KB Output is correct
11 Correct 1835 ms 24256 KB Output is correct
12 Correct 35 ms 3408 KB Output is correct
13 Execution timed out 3573 ms 30548 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3416 KB Output is correct
2 Correct 59 ms 4436 KB Output is correct
3 Correct 47 ms 4604 KB Output is correct
4 Correct 104 ms 4512 KB Output is correct
5 Correct 75 ms 4920 KB Output is correct
6 Correct 42 ms 4692 KB Output is correct
7 Correct 30 ms 3436 KB Output is correct
8 Correct 720 ms 21844 KB Output is correct
9 Correct 715 ms 21840 KB Output is correct
10 Correct 42 ms 3548 KB Output is correct
11 Correct 1354 ms 30800 KB Output is correct
12 Correct 1389 ms 30896 KB Output is correct
13 Correct 609 ms 30944 KB Output is correct
14 Correct 31 ms 3416 KB Output is correct
15 Correct 532 ms 21328 KB Output is correct
16 Correct 1435 ms 21324 KB Output is correct
17 Correct 1890 ms 22416 KB Output is correct
18 Correct 1506 ms 22360 KB Output is correct
19 Correct 1477 ms 24912 KB Output is correct
20 Correct 1722 ms 24300 KB Output is correct
21 Correct 770 ms 22352 KB Output is correct
22 Correct 805 ms 22412 KB Output is correct
23 Correct 911 ms 22700 KB Output is correct
24 Correct 922 ms 22664 KB Output is correct
25 Correct 1447 ms 24656 KB Output is correct
26 Correct 2145 ms 21844 KB Output is correct
27 Correct 2142 ms 21840 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3416 KB Output is correct
2 Correct 59 ms 4436 KB Output is correct
3 Correct 47 ms 4604 KB Output is correct
4 Correct 104 ms 4512 KB Output is correct
5 Correct 75 ms 4920 KB Output is correct
6 Correct 42 ms 4692 KB Output is correct
7 Correct 30 ms 3436 KB Output is correct
8 Correct 720 ms 21844 KB Output is correct
9 Correct 715 ms 21840 KB Output is correct
10 Correct 42 ms 3548 KB Output is correct
11 Correct 1354 ms 30800 KB Output is correct
12 Correct 1389 ms 30896 KB Output is correct
13 Correct 609 ms 30944 KB Output is correct
14 Correct 31 ms 3416 KB Output is correct
15 Correct 532 ms 21328 KB Output is correct
16 Correct 1435 ms 21324 KB Output is correct
17 Correct 1890 ms 22416 KB Output is correct
18 Correct 1506 ms 22360 KB Output is correct
19 Correct 1477 ms 24912 KB Output is correct
20 Correct 1722 ms 24300 KB Output is correct
21 Correct 770 ms 22352 KB Output is correct
22 Correct 805 ms 22412 KB Output is correct
23 Correct 911 ms 22700 KB Output is correct
24 Correct 922 ms 22664 KB Output is correct
25 Correct 1447 ms 24656 KB Output is correct
26 Correct 2145 ms 21844 KB Output is correct
27 Correct 2142 ms 21840 KB Output is correct
28 Correct 44 ms 3412 KB Output is correct
29 Incorrect 97 ms 4240 KB Extra information in the output file
30 Halted 0 ms 0 KB -