oj.uz

Submission #1042402

# Submission time Handle Problem Language Result Execution time Memory
1042402 2024-08-03T03:47:59 Z sleepntsheep Inside information (BOI21_servers) C
62.5 / 100
 3500 ms 27704 KB 
    #include <stdio.h>
    #include <stdlib.h>
     
    #define N 120001
    #define B 700
     
     
    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') {
                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:13:30: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   13 |         else if (0 == (o & o - 1)) eh[i] = (int*)realloc(eh[i], 2 * o * sizeof **eh);
      |                            ~~^~~
servers.c: In function 'main':
servers.c:110:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         scanf("%d%d", &n, &q);
      |         ^~~~~~~~~~~~~~~~~~~~~
servers.c:116:13: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |             scanf(" %c%d", &c, &a);
      |             ^~~~~~~~~~~~~~~~~~~~~~
servers.c:118:17: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |                 scanf("%d", &b);
      |                 ^~~~~~~~~~~~~~~
servers.c:122:17: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |                 scanf("%d", &b);
      |                 ^~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2652 KB Output is correct
2 Correct 23 ms 3104 KB Output is correct
3 Correct 19 ms 5208 KB Output is correct
4 Correct 39 ms 3152 KB Output is correct
5 Correct 43 ms 3412 KB Output is correct
6 Correct 18 ms 3164 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2652 KB Output is correct
2 Correct 23 ms 3104 KB Output is correct
3 Correct 19 ms 5208 KB Output is correct
4 Correct 39 ms 3152 KB Output is correct
5 Correct 43 ms 3412 KB Output is correct
6 Correct 18 ms 3164 KB Output is correct
7 Correct 426 ms 2724 KB Output is correct
8 Correct 1674 ms 3408 KB Output is correct
9 Correct 1744 ms 4356 KB Output is correct
10 Execution timed out 3579 ms 4180 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2648 KB Output is correct
2 Correct 240 ms 19008 KB Output is correct
3 Correct 254 ms 19028 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2648 KB Output is correct
2 Correct 240 ms 19008 KB Output is correct
3 Correct 254 ms 19028 KB Output is correct
4 Correct 389 ms 2640 KB Output is correct
5 Correct 384 ms 19480 KB Output is correct
6 Correct 668 ms 21332 KB Output is correct
7 Correct 866 ms 21568 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2648 KB Output is correct
2 Correct 421 ms 27448 KB Output is correct
3 Correct 421 ms 27584 KB Output is correct
4 Correct 237 ms 27380 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2648 KB Output is correct
2 Correct 421 ms 27448 KB Output is correct
3 Correct 421 ms 27584 KB Output is correct
4 Correct 237 ms 27380 KB Output is correct
5 Correct 407 ms 2640 KB Output is correct
6 Execution timed out 3576 ms 27576 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2648 KB Output is correct
2 Correct 173 ms 18000 KB Output is correct
3 Correct 410 ms 18000 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2648 KB Output is correct
2 Correct 173 ms 18000 KB Output is correct
3 Correct 410 ms 18000 KB Output is correct
4 Correct 412 ms 2900 KB Output is correct
5 Correct 1296 ms 18532 KB Output is correct
6 Correct 2246 ms 21468 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2908 KB Output is correct
2 Correct 409 ms 27596 KB Output is correct
3 Correct 432 ms 27476 KB Output is correct
4 Correct 222 ms 27476 KB Output is correct
5 Correct 15 ms 2904 KB Output is correct
6 Correct 169 ms 18004 KB Output is correct
7 Correct 407 ms 18004 KB Output is correct
8 Correct 507 ms 19024 KB Output is correct
9 Correct 440 ms 19284 KB Output is correct
10 Correct 468 ms 21588 KB Output is correct
11 Correct 493 ms 20836 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2908 KB Output is correct
2 Correct 409 ms 27596 KB Output is correct
3 Correct 432 ms 27476 KB Output is correct
4 Correct 222 ms 27476 KB Output is correct
5 Correct 15 ms 2904 KB Output is correct
6 Correct 169 ms 18004 KB Output is correct
7 Correct 407 ms 18004 KB Output is correct
8 Correct 507 ms 19024 KB Output is correct
9 Correct 440 ms 19284 KB Output is correct
10 Correct 468 ms 21588 KB Output is correct
11 Correct 493 ms 20836 KB Output is correct
12 Correct 422 ms 2900 KB Output is correct
13 Execution timed out 3555 ms 27472 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2648 KB Output is correct
2 Correct 26 ms 3212 KB Output is correct
3 Correct 22 ms 3352 KB Output is correct
4 Correct 37 ms 3524 KB Output is correct
5 Correct 37 ms 5456 KB Output is correct
6 Correct 19 ms 3152 KB Output is correct
7 Correct 16 ms 2652 KB Output is correct
8 Correct 249 ms 19540 KB Output is correct
9 Correct 241 ms 19024 KB Output is correct
10 Correct 16 ms 2908 KB Output is correct
11 Correct 419 ms 27704 KB Output is correct
12 Correct 415 ms 27472 KB Output is correct
13 Correct 229 ms 27476 KB Output is correct
14 Correct 15 ms 2652 KB Output is correct
15 Correct 167 ms 18068 KB Output is correct
16 Correct 420 ms 18004 KB Output is correct
17 Correct 535 ms 19028 KB Output is correct
18 Correct 498 ms 19080 KB Output is correct
19 Correct 464 ms 21588 KB Output is correct
20 Correct 517 ms 20816 KB Output is correct
21 Correct 269 ms 19028 KB Output is correct
22 Correct 285 ms 19120 KB Output is correct
23 Correct 301 ms 19536 KB Output is correct
24 Correct 306 ms 19536 KB Output is correct
25 Correct 439 ms 21328 KB Output is correct
26 Correct 544 ms 18512 KB Output is correct
27 Correct 523 ms 18512 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2648 KB Output is correct
2 Correct 26 ms 3212 KB Output is correct
3 Correct 22 ms 3352 KB Output is correct
4 Correct 37 ms 3524 KB Output is correct
5 Correct 37 ms 5456 KB Output is correct
6 Correct 19 ms 3152 KB Output is correct
7 Correct 16 ms 2652 KB Output is correct
8 Correct 249 ms 19540 KB Output is correct
9 Correct 241 ms 19024 KB Output is correct
10 Correct 16 ms 2908 KB Output is correct
11 Correct 419 ms 27704 KB Output is correct
12 Correct 415 ms 27472 KB Output is correct
13 Correct 229 ms 27476 KB Output is correct
14 Correct 15 ms 2652 KB Output is correct
15 Correct 167 ms 18068 KB Output is correct
16 Correct 420 ms 18004 KB Output is correct
17 Correct 535 ms 19028 KB Output is correct
18 Correct 498 ms 19080 KB Output is correct
19 Correct 464 ms 21588 KB Output is correct
20 Correct 517 ms 20816 KB Output is correct
21 Correct 269 ms 19028 KB Output is correct
22 Correct 285 ms 19120 KB Output is correct
23 Correct 301 ms 19536 KB Output is correct
24 Correct 306 ms 19536 KB Output is correct
25 Correct 439 ms 21328 KB Output is correct
26 Correct 544 ms 18512 KB Output is correct
27 Correct 523 ms 18512 KB Output is correct
28 Correct 408 ms 2900 KB Output is correct
29 Correct 1703 ms 3156 KB Output is correct
30 Correct 1643 ms 4436 KB Output is correct
31 Execution timed out 3558 ms 4364 KB Time limit exceeded
32 Halted 0 ms 0 KB -