oj.uz

Submission #1042413

# Submission time Handle Problem Language Result Execution time Memory
1042413 2024-08-03T04:03:58 Z sleepntsheep Inside information (BOI21_servers) C
50 / 100
 3141 ms 26392 KB 
/* WHAT IS EXTRA INFORAMZTION GTR RR */

#include <stdio.h>
#include <stdlib.h>

int max(int i, int j) { return i > j ? i : j; }
/*
 * 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] = max(y + 1, dp[qq[i].a]);
        dp[qq[i].b] = max(x + 1, dp[qq[i].b]);
    }

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

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 2652 KB Output is correct
2 Correct 73 ms 2720 KB Output is correct
3 Correct 64 ms 2748 KB Output is correct
4 Correct 101 ms 2640 KB Output is correct
5 Correct 133 ms 2900 KB Output is correct
6 Correct 50 ms 2648 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 2652 KB Output is correct
2 Correct 73 ms 2720 KB Output is correct
3 Correct 64 ms 2748 KB Output is correct
4 Correct 101 ms 2640 KB Output is correct
5 Correct 133 ms 2900 KB Output is correct
6 Correct 50 ms 2648 KB Output is correct
7 Incorrect 637 ms 2220 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 37 ms 2900 KB Output is correct
2 Correct 1075 ms 17720 KB Output is correct
3 Correct 1111 ms 17828 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 2900 KB Output is correct
2 Correct 1075 ms 17720 KB Output is correct
3 Correct 1111 ms 17828 KB Output is correct
4 Incorrect 666 ms 2128 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 78 ms 2640 KB Output is correct
2 Correct 2384 ms 26180 KB Output is correct
3 Correct 2306 ms 26392 KB Output is correct
4 Correct 815 ms 26016 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 2640 KB Output is correct
2 Correct 2384 ms 26180 KB Output is correct
3 Correct 2306 ms 26392 KB Output is correct
4 Correct 815 ms 26016 KB Output is correct
5 Incorrect 626 ms 2388 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 35 ms 2136 KB Output is correct
2 Correct 699 ms 16884 KB Output is correct
3 Correct 2583 ms 16764 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2136 KB Output is correct
2 Correct 699 ms 16884 KB Output is correct
3 Correct 2583 ms 16764 KB Output is correct
4 Incorrect 640 ms 2384 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 37 ms 2148 KB Output is correct
2 Correct 2277 ms 26192 KB Output is correct
3 Correct 2444 ms 25984 KB Output is correct
4 Correct 894 ms 25936 KB Output is correct
5 Correct 37 ms 2140 KB Output is correct
6 Correct 809 ms 16940 KB Output is correct
7 Correct 2915 ms 16788 KB Output is correct
8 Correct 3062 ms 17692 KB Output is correct
9 Correct 2125 ms 17700 KB Output is correct
10 Correct 1839 ms 20168 KB Output is correct
11 Correct 2206 ms 19576 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 2148 KB Output is correct
2 Correct 2277 ms 26192 KB Output is correct
3 Correct 2444 ms 25984 KB Output is correct
4 Correct 894 ms 25936 KB Output is correct
5 Correct 37 ms 2140 KB Output is correct
6 Correct 809 ms 16940 KB Output is correct
7 Correct 2915 ms 16788 KB Output is correct
8 Correct 3062 ms 17692 KB Output is correct
9 Correct 2125 ms 17700 KB Output is correct
10 Correct 1839 ms 20168 KB Output is correct
11 Correct 2206 ms 19576 KB Output is correct
12 Incorrect 593 ms 2712 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 35 ms 2128 KB Output is correct
2 Correct 68 ms 2668 KB Output is correct
3 Correct 57 ms 2760 KB Output is correct
4 Correct 99 ms 2640 KB Output is correct
5 Correct 92 ms 3024 KB Output is correct
6 Correct 50 ms 2648 KB Output is correct
7 Correct 35 ms 2140 KB Output is correct
8 Correct 1018 ms 17616 KB Output is correct
9 Correct 990 ms 17744 KB Output is correct
10 Correct 37 ms 2132 KB Output is correct
11 Correct 1775 ms 26104 KB Output is correct
12 Correct 1731 ms 26200 KB Output is correct
13 Correct 801 ms 25940 KB Output is correct
14 Correct 35 ms 2648 KB Output is correct
15 Correct 696 ms 16532 KB Output is correct
16 Correct 1959 ms 16580 KB Output is correct
17 Correct 2498 ms 17688 KB Output is correct
18 Correct 1953 ms 17796 KB Output is correct
19 Correct 1928 ms 20052 KB Output is correct
20 Correct 2329 ms 19572 KB Output is correct
21 Correct 998 ms 17748 KB Output is correct
22 Correct 1025 ms 17744 KB Output is correct
23 Correct 1220 ms 18108 KB Output is correct
24 Correct 1206 ms 18000 KB Output is correct
25 Correct 1956 ms 19968 KB Output is correct
26 Correct 3135 ms 17088 KB Output is correct
27 Correct 3141 ms 17024 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2128 KB Output is correct
2 Correct 68 ms 2668 KB Output is correct
3 Correct 57 ms 2760 KB Output is correct
4 Correct 99 ms 2640 KB Output is correct
5 Correct 92 ms 3024 KB Output is correct
6 Correct 50 ms 2648 KB Output is correct
7 Correct 35 ms 2140 KB Output is correct
8 Correct 1018 ms 17616 KB Output is correct
9 Correct 990 ms 17744 KB Output is correct
10 Correct 37 ms 2132 KB Output is correct
11 Correct 1775 ms 26104 KB Output is correct
12 Correct 1731 ms 26200 KB Output is correct
13 Correct 801 ms 25940 KB Output is correct
14 Correct 35 ms 2648 KB Output is correct
15 Correct 696 ms 16532 KB Output is correct
16 Correct 1959 ms 16580 KB Output is correct
17 Correct 2498 ms 17688 KB Output is correct
18 Correct 1953 ms 17796 KB Output is correct
19 Correct 1928 ms 20052 KB Output is correct
20 Correct 2329 ms 19572 KB Output is correct
21 Correct 998 ms 17748 KB Output is correct
22 Correct 1025 ms 17744 KB Output is correct
23 Correct 1220 ms 18108 KB Output is correct
24 Correct 1206 ms 18000 KB Output is correct
25 Correct 1956 ms 19968 KB Output is correct
26 Correct 3135 ms 17088 KB Output is correct
27 Correct 3141 ms 17024 KB Output is correct
28 Incorrect 607 ms 2640 KB Extra information in the output file
29 Halted 0 ms 0 KB -