oj.uz

Submission #1042410

# Submission time Handle Problem Language Result Execution time Memory
1042410 2024-08-03T04:00:21 Z sleepntsheep Inside information (BOI21_servers) C
50 / 100
 3500 ms 30592 KB 
        #include <stdio.h>
        #include <stdlib.h>
         
        #define N 120001
        #define B 700
         
         int max(int i, int j) {return i > j ? i : j;}

        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] = max(dp[qq[i].a], y + 1);
        dp[qq[i].b] = max(dp[qq[i].b], x + 1);
            }
         
            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') {
                    if (j % B == 0) {
                        build(map_time[j], j);
                        at = map_time[j] + 1;
                    }
                    ++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);
                }
            }
        }

Compilation message

servers.c: In function 'pus_':
servers.c:14:34: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   14 |             else if (0 == (o & o - 1)) eh[i] = (int*)realloc(eh[i], 2 * o * sizeof **eh);
      |                                ~~^~~
servers.c: In function 'main':
servers.c:111:13: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |             scanf("%d%d", &n, &q);
      |             ^~~~~~~~~~~~~~~~~~~~~
servers.c:117:17: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |                 scanf(" %c%d", &c, &a);
      |                 ^~~~~~~~~~~~~~~~~~~~~~
servers.c:119:21: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |                     scanf("%d", &b);
      |                     ^~~~~~~~~~~~~~~
servers.c:123:21: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |                     scanf("%d", &b);
      |                     ^~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2908 KB Output is correct
2 Correct 27 ms 3192 KB Output is correct
3 Correct 20 ms 3164 KB Output is correct
4 Correct 38 ms 3196 KB Output is correct
5 Correct 36 ms 3408 KB Output is correct
6 Correct 22 ms 3160 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2908 KB Output is correct
2 Correct 27 ms 3192 KB Output is correct
3 Correct 20 ms 3164 KB Output is correct
4 Correct 38 ms 3196 KB Output is correct
5 Correct 36 ms 3408 KB Output is correct
6 Correct 22 ms 3160 KB Output is correct
7 Correct 415 ms 2896 KB Output is correct
8 Incorrect 1736 ms 4176 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 15 ms 2904 KB Output is correct
2 Correct 259 ms 19284 KB Output is correct
3 Correct 251 ms 19028 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2904 KB Output is correct
2 Correct 259 ms 19284 KB Output is correct
3 Correct 251 ms 19028 KB Output is correct
4 Correct 408 ms 2640 KB Output is correct
5 Incorrect 390 ms 22164 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 18 ms 2648 KB Output is correct
2 Correct 482 ms 27472 KB Output is correct
3 Correct 434 ms 27728 KB Output is correct
4 Correct 240 ms 27476 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2648 KB Output is correct
2 Correct 482 ms 27472 KB Output is correct
3 Correct 434 ms 27728 KB Output is correct
4 Correct 240 ms 27476 KB Output is correct
5 Correct 482 ms 2904 KB Output is correct
6 Execution timed out 3575 ms 30532 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2904 KB Output is correct
2 Correct 178 ms 18152 KB Output is correct
3 Correct 441 ms 18000 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2904 KB Output is correct
2 Correct 178 ms 18152 KB Output is correct
3 Correct 441 ms 18000 KB Output is correct
4 Correct 403 ms 2928 KB Output is correct
5 Incorrect 1297 ms 21376 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 22 ms 2908 KB Output is correct
2 Correct 447 ms 27392 KB Output is correct
3 Correct 450 ms 27748 KB Output is correct
4 Correct 235 ms 27472 KB Output is correct
5 Correct 17 ms 2904 KB Output is correct
6 Correct 181 ms 18064 KB Output is correct
7 Correct 430 ms 18212 KB Output is correct
8 Correct 570 ms 19100 KB Output is correct
9 Correct 451 ms 19028 KB Output is correct
10 Correct 493 ms 21584 KB Output is correct
11 Correct 503 ms 21076 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2908 KB Output is correct
2 Correct 447 ms 27392 KB Output is correct
3 Correct 450 ms 27748 KB Output is correct
4 Correct 235 ms 27472 KB Output is correct
5 Correct 17 ms 2904 KB Output is correct
6 Correct 181 ms 18064 KB Output is correct
7 Correct 430 ms 18212 KB Output is correct
8 Correct 570 ms 19100 KB Output is correct
9 Correct 451 ms 19028 KB Output is correct
10 Correct 493 ms 21584 KB Output is correct
11 Correct 503 ms 21076 KB Output is correct
12 Correct 447 ms 2956 KB Output is correct
13 Execution timed out 3575 ms 30592 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2908 KB Output is correct
2 Correct 27 ms 3204 KB Output is correct
3 Correct 20 ms 3264 KB Output is correct
4 Correct 38 ms 3160 KB Output is correct
5 Correct 37 ms 3480 KB Output is correct
6 Correct 18 ms 3164 KB Output is correct
7 Correct 15 ms 2684 KB Output is correct
8 Correct 255 ms 19028 KB Output is correct
9 Correct 265 ms 18952 KB Output is correct
10 Correct 15 ms 2904 KB Output is correct
11 Correct 424 ms 27464 KB Output is correct
12 Correct 435 ms 27432 KB Output is correct
13 Correct 234 ms 27448 KB Output is correct
14 Correct 18 ms 2652 KB Output is correct
15 Correct 206 ms 17948 KB Output is correct
16 Correct 449 ms 18160 KB Output is correct
17 Correct 536 ms 19024 KB Output is correct
18 Correct 479 ms 19284 KB Output is correct
19 Correct 485 ms 21584 KB Output is correct
20 Correct 513 ms 20964 KB Output is correct
21 Correct 265 ms 19028 KB Output is correct
22 Correct 265 ms 19024 KB Output is correct
23 Correct 294 ms 19540 KB Output is correct
24 Correct 309 ms 19568 KB Output is correct
25 Correct 458 ms 21324 KB Output is correct
26 Correct 557 ms 18304 KB Output is correct
27 Correct 573 ms 18516 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2908 KB Output is correct
2 Correct 27 ms 3204 KB Output is correct
3 Correct 20 ms 3264 KB Output is correct
4 Correct 38 ms 3160 KB Output is correct
5 Correct 37 ms 3480 KB Output is correct
6 Correct 18 ms 3164 KB Output is correct
7 Correct 15 ms 2684 KB Output is correct
8 Correct 255 ms 19028 KB Output is correct
9 Correct 265 ms 18952 KB Output is correct
10 Correct 15 ms 2904 KB Output is correct
11 Correct 424 ms 27464 KB Output is correct
12 Correct 435 ms 27432 KB Output is correct
13 Correct 234 ms 27448 KB Output is correct
14 Correct 18 ms 2652 KB Output is correct
15 Correct 206 ms 17948 KB Output is correct
16 Correct 449 ms 18160 KB Output is correct
17 Correct 536 ms 19024 KB Output is correct
18 Correct 479 ms 19284 KB Output is correct
19 Correct 485 ms 21584 KB Output is correct
20 Correct 513 ms 20964 KB Output is correct
21 Correct 265 ms 19028 KB Output is correct
22 Correct 265 ms 19024 KB Output is correct
23 Correct 294 ms 19540 KB Output is correct
24 Correct 309 ms 19568 KB Output is correct
25 Correct 458 ms 21324 KB Output is correct
26 Correct 557 ms 18304 KB Output is correct
27 Correct 573 ms 18516 KB Output is correct
28 Correct 434 ms 2776 KB Output is correct
29 Incorrect 1663 ms 4212 KB Extra information in the output file
30 Halted 0 ms 0 KB -