oj.uz

Submission #1042404

# Submission time Handle Problem Language Result Execution time Memory
1042404 2024-08-03T03:51:38 Z sleepntsheep Inside information (BOI21_servers) C
52.5 / 100
 3500 ms 29540 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;
    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 (i % B == 0) {
            build(i, j);
            at = i + 1;
        }

        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: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 22 ms 2904 KB Output is correct
2 Correct 42 ms 3920 KB Output is correct
3 Correct 42 ms 4176 KB Output is correct
4 Correct 61 ms 3980 KB Output is correct
5 Correct 57 ms 4416 KB Output is correct
6 Correct 36 ms 4180 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2904 KB Output is correct
2 Correct 42 ms 3920 KB Output is correct
3 Correct 42 ms 4176 KB Output is correct
4 Correct 61 ms 3980 KB Output is correct
5 Correct 57 ms 4416 KB Output is correct
6 Correct 36 ms 4180 KB Output is correct
7 Correct 25 ms 2908 KB Output is correct
8 Incorrect 89 ms 3668 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 21 ms 3676 KB Output is correct
2 Correct 419 ms 20304 KB Output is correct
3 Correct 429 ms 20136 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3676 KB Output is correct
2 Correct 419 ms 20304 KB Output is correct
3 Correct 429 ms 20136 KB Output is correct
4 Correct 22 ms 2908 KB Output is correct
5 Correct 507 ms 20772 KB Output is correct
6 Correct 621 ms 20072 KB Output is correct
7 Correct 719 ms 20308 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2904 KB Output is correct
2 Correct 850 ms 29012 KB Output is correct
3 Correct 777 ms 29520 KB Output is correct
4 Correct 366 ms 29396 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2904 KB Output is correct
2 Correct 850 ms 29012 KB Output is correct
3 Correct 777 ms 29520 KB Output is correct
4 Correct 366 ms 29396 KB Output is correct
5 Correct 28 ms 3676 KB Output is correct
6 Execution timed out 3542 ms 29208 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3672 KB Output is correct
2 Correct 312 ms 20040 KB Output is correct
3 Correct 854 ms 20048 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3672 KB Output is correct
2 Correct 312 ms 20040 KB Output is correct
3 Correct 854 ms 20048 KB Output is correct
4 Correct 22 ms 3016 KB Output is correct
5 Incorrect 554 ms 20052 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 2908 KB Output is correct
2 Correct 824 ms 29368 KB Output is correct
3 Correct 776 ms 29528 KB Output is correct
4 Correct 403 ms 29268 KB Output is correct
5 Correct 22 ms 3676 KB Output is correct
6 Correct 309 ms 19936 KB Output is correct
7 Correct 885 ms 20168 KB Output is correct
8 Correct 1175 ms 21072 KB Output is correct
9 Correct 975 ms 21120 KB Output is correct
10 Correct 1173 ms 23548 KB Output is correct
11 Correct 1395 ms 22868 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2908 KB Output is correct
2 Correct 824 ms 29368 KB Output is correct
3 Correct 776 ms 29528 KB Output is correct
4 Correct 403 ms 29268 KB Output is correct
5 Correct 22 ms 3676 KB Output is correct
6 Correct 309 ms 19936 KB Output is correct
7 Correct 885 ms 20168 KB Output is correct
8 Correct 1175 ms 21072 KB Output is correct
9 Correct 975 ms 21120 KB Output is correct
10 Correct 1173 ms 23548 KB Output is correct
11 Correct 1395 ms 22868 KB Output is correct
12 Correct 33 ms 2904 KB Output is correct
13 Execution timed out 3543 ms 29232 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 3012 KB Output is correct
2 Correct 72 ms 4028 KB Output is correct
3 Correct 35 ms 4196 KB Output is correct
4 Correct 61 ms 4160 KB Output is correct
5 Correct 57 ms 4356 KB Output is correct
6 Correct 30 ms 4176 KB Output is correct
7 Correct 28 ms 3156 KB Output is correct
8 Correct 501 ms 20564 KB Output is correct
9 Correct 512 ms 20392 KB Output is correct
10 Correct 24 ms 3704 KB Output is correct
11 Correct 1024 ms 29488 KB Output is correct
12 Correct 1047 ms 29404 KB Output is correct
13 Correct 374 ms 29540 KB Output is correct
14 Correct 22 ms 2904 KB Output is correct
15 Correct 357 ms 19880 KB Output is correct
16 Correct 1152 ms 20008 KB Output is correct
17 Correct 1553 ms 20956 KB Output is correct
18 Correct 1008 ms 21072 KB Output is correct
19 Correct 1018 ms 23680 KB Output is correct
20 Correct 1401 ms 22836 KB Output is correct
21 Correct 538 ms 21072 KB Output is correct
22 Correct 500 ms 21016 KB Output is correct
23 Correct 668 ms 21356 KB Output is correct
24 Correct 662 ms 21356 KB Output is correct
25 Correct 886 ms 23120 KB Output is correct
26 Correct 1454 ms 20500 KB Output is correct
27 Correct 1415 ms 20460 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 3012 KB Output is correct
2 Correct 72 ms 4028 KB Output is correct
3 Correct 35 ms 4196 KB Output is correct
4 Correct 61 ms 4160 KB Output is correct
5 Correct 57 ms 4356 KB Output is correct
6 Correct 30 ms 4176 KB Output is correct
7 Correct 28 ms 3156 KB Output is correct
8 Correct 501 ms 20564 KB Output is correct
9 Correct 512 ms 20392 KB Output is correct
10 Correct 24 ms 3704 KB Output is correct
11 Correct 1024 ms 29488 KB Output is correct
12 Correct 1047 ms 29404 KB Output is correct
13 Correct 374 ms 29540 KB Output is correct
14 Correct 22 ms 2904 KB Output is correct
15 Correct 357 ms 19880 KB Output is correct
16 Correct 1152 ms 20008 KB Output is correct
17 Correct 1553 ms 20956 KB Output is correct
18 Correct 1008 ms 21072 KB Output is correct
19 Correct 1018 ms 23680 KB Output is correct
20 Correct 1401 ms 22836 KB Output is correct
21 Correct 538 ms 21072 KB Output is correct
22 Correct 500 ms 21016 KB Output is correct
23 Correct 668 ms 21356 KB Output is correct
24 Correct 662 ms 21356 KB Output is correct
25 Correct 886 ms 23120 KB Output is correct
26 Correct 1454 ms 20500 KB Output is correct
27 Correct 1415 ms 20460 KB Output is correct
28 Correct 24 ms 2936 KB Output is correct
29 Incorrect 93 ms 3608 KB Extra information in the output file
30 Halted 0 ms 0 KB -