oj.uz

Submission #1042382

# Submission time Handle Problem Language Result Execution time Memory
1042382 2024-08-03T03:14:36 Z sleepntsheep Inside information (BOI21_servers) C
62.5 / 100
 3500 ms 30492 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:26: 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:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |     scanf("%d%d", &n, &q);
      |     ^~~~~~~~~~~~~~~~~~~~~
servers.c:116:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         scanf(" %c%d", &c, &a);
      |         ^~~~~~~~~~~~~~~~~~~~~~
servers.c:118:13: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |             scanf("%d", &b);
      |             ^~~~~~~~~~~~~~~
servers.c:122:13: 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 15 ms 2908 KB Output is correct
2 Correct 23 ms 3040 KB Output is correct
3 Correct 19 ms 3164 KB Output is correct
4 Correct 38 ms 3232 KB Output is correct
5 Correct 37 ms 3420 KB Output is correct
6 Correct 23 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 23 ms 3040 KB Output is correct
3 Correct 19 ms 3164 KB Output is correct
4 Correct 38 ms 3232 KB Output is correct
5 Correct 37 ms 3420 KB Output is correct
6 Correct 23 ms 3160 KB Output is correct
7 Correct 412 ms 2856 KB Output is correct
8 Correct 1720 ms 4280 KB Output is correct
9 Correct 1640 ms 4444 KB Output is correct
10 Execution timed out 3567 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 15 ms 2904 KB Output is correct
2 Correct 244 ms 19024 KB Output is correct
3 Correct 237 ms 19028 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2904 KB Output is correct
2 Correct 244 ms 19024 KB Output is correct
3 Correct 237 ms 19028 KB Output is correct
4 Correct 415 ms 3156 KB Output is correct
5 Correct 379 ms 22100 KB Output is correct
6 Correct 639 ms 21764 KB Output is correct
7 Correct 839 ms 21588 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2908 KB Output is correct
2 Correct 425 ms 27476 KB Output is correct
3 Correct 447 ms 27480 KB Output is correct
4 Correct 228 ms 27472 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2908 KB Output is correct
2 Correct 425 ms 27476 KB Output is correct
3 Correct 447 ms 27480 KB Output is correct
4 Correct 228 ms 27472 KB Output is correct
5 Correct 406 ms 2900 KB Output is correct
6 Execution timed out 3569 ms 30492 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 2908 KB Output is correct
2 Correct 172 ms 18088 KB Output is correct
3 Correct 422 ms 18080 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2908 KB Output is correct
2 Correct 172 ms 18088 KB Output is correct
3 Correct 422 ms 18080 KB Output is correct
4 Correct 429 ms 2480 KB Output is correct
5 Correct 1318 ms 21332 KB Output is correct
6 Correct 2240 ms 21468 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2904 KB Output is correct
2 Correct 432 ms 27476 KB Output is correct
3 Correct 414 ms 27728 KB Output is correct
4 Correct 251 ms 27472 KB Output is correct
5 Correct 15 ms 2908 KB Output is correct
6 Correct 165 ms 18000 KB Output is correct
7 Correct 417 ms 18272 KB Output is correct
8 Correct 519 ms 19100 KB Output is correct
9 Correct 458 ms 19156 KB Output is correct
10 Correct 527 ms 21648 KB Output is correct
11 Correct 504 ms 20768 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2904 KB Output is correct
2 Correct 432 ms 27476 KB Output is correct
3 Correct 414 ms 27728 KB Output is correct
4 Correct 251 ms 27472 KB Output is correct
5 Correct 15 ms 2908 KB Output is correct
6 Correct 165 ms 18000 KB Output is correct
7 Correct 417 ms 18272 KB Output is correct
8 Correct 519 ms 19100 KB Output is correct
9 Correct 458 ms 19156 KB Output is correct
10 Correct 527 ms 21648 KB Output is correct
11 Correct 504 ms 20768 KB Output is correct
12 Correct 401 ms 2644 KB Output is correct
13 Execution timed out 3552 ms 30440 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2648 KB Output is correct
2 Correct 23 ms 3164 KB Output is correct
3 Correct 19 ms 3164 KB Output is correct
4 Correct 38 ms 3196 KB Output is correct
5 Correct 38 ms 3408 KB Output is correct
6 Correct 18 ms 3164 KB Output is correct
7 Correct 15 ms 2652 KB Output is correct
8 Correct 238 ms 19024 KB Output is correct
9 Correct 242 ms 19024 KB Output is correct
10 Correct 15 ms 2652 KB Output is correct
11 Correct 415 ms 27448 KB Output is correct
12 Correct 424 ms 27476 KB Output is correct
13 Correct 234 ms 27440 KB Output is correct
14 Correct 15 ms 2904 KB Output is correct
15 Correct 161 ms 18184 KB Output is correct
16 Correct 414 ms 18260 KB Output is correct
17 Correct 556 ms 19080 KB Output is correct
18 Correct 459 ms 19200 KB Output is correct
19 Correct 467 ms 21588 KB Output is correct
20 Correct 553 ms 20820 KB Output is correct
21 Correct 253 ms 19356 KB Output is correct
22 Correct 261 ms 19012 KB Output is correct
23 Correct 320 ms 19536 KB Output is correct
24 Correct 297 ms 19544 KB Output is correct
25 Correct 447 ms 21588 KB Output is correct
26 Correct 560 ms 18516 KB Output is correct
27 Correct 531 ms 18428 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2648 KB Output is correct
2 Correct 23 ms 3164 KB Output is correct
3 Correct 19 ms 3164 KB Output is correct
4 Correct 38 ms 3196 KB Output is correct
5 Correct 38 ms 3408 KB Output is correct
6 Correct 18 ms 3164 KB Output is correct
7 Correct 15 ms 2652 KB Output is correct
8 Correct 238 ms 19024 KB Output is correct
9 Correct 242 ms 19024 KB Output is correct
10 Correct 15 ms 2652 KB Output is correct
11 Correct 415 ms 27448 KB Output is correct
12 Correct 424 ms 27476 KB Output is correct
13 Correct 234 ms 27440 KB Output is correct
14 Correct 15 ms 2904 KB Output is correct
15 Correct 161 ms 18184 KB Output is correct
16 Correct 414 ms 18260 KB Output is correct
17 Correct 556 ms 19080 KB Output is correct
18 Correct 459 ms 19200 KB Output is correct
19 Correct 467 ms 21588 KB Output is correct
20 Correct 553 ms 20820 KB Output is correct
21 Correct 253 ms 19356 KB Output is correct
22 Correct 261 ms 19012 KB Output is correct
23 Correct 320 ms 19536 KB Output is correct
24 Correct 297 ms 19544 KB Output is correct
25 Correct 447 ms 21588 KB Output is correct
26 Correct 560 ms 18516 KB Output is correct
27 Correct 531 ms 18428 KB Output is correct
28 Correct 410 ms 2956 KB Output is correct
29 Correct 1679 ms 4176 KB Output is correct
30 Correct 1669 ms 6224 KB Output is correct
31 Execution timed out 3546 ms 4176 KB Time limit exceeded
32 Halted 0 ms 0 KB -