oj.uz

Submission #1042371

# Submission time Handle Problem Language Result Execution time Memory
1042371 2024-08-03T02:59:18 Z sleepntsheep Inside information (BOI21_servers) C
50 / 100
 108 ms 29716 KB 
#include <stdio.h>
#include <stdlib.h>

int max(int i, int j){ return i > j ? i : j; }
#define N 120001

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;
    int a, b;
    int ans;
} qq[N * 2];

/* v = ask node, u = data node */
int query_yesno(int u, int v, int time) {
    if (u == v) return 1;
    int a = lca(u, v);
    //printf("(%d %d %d %d)\n",u,v,time,a);
    int va = anc(v, dd[a] + 1);
    int ua = anc(u, dd[a] + 1);

    if (u == a) {
        //printf("%d\n",up[v]);
        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 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++);
        } else if (c == 'Q') {
            scanf("%d", &b);
        } else {
        }

        qq[i] = (struct Query){c, a, b};
    }

    up[1] = 1e9;
    pp[1] = jj[1] = 1;
    dfs(1, 1);

    for (int j = 0, i = 0; i < q; ++i) {
        if (qq[i].type == 'S') ++j;
        if (qq[i].type == 'Q') {
            puts(query_yesno(qq[i].b, qq[i].a, j - 1) ? "yes": "no");
        }
    }
}

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:85:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |     scanf("%d%d", &n, &q);
      |     ^~~~~~~~~~~~~~~~~~~~~
servers.c:91:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         scanf(" %c%d", &c, &a);
      |         ^~~~~~~~~~~~~~~~~~~~~~
servers.c:93:13: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |             scanf("%d", &b);
      |             ^~~~~~~~~~~~~~~
servers.c:96:13: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |             scanf("%d", &b);
      |             ^~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 5980 KB Output is correct
2 Correct 23 ms 7772 KB Output is correct
3 Correct 23 ms 7760 KB Output is correct
4 Correct 39 ms 7828 KB Output is correct
5 Correct 38 ms 8020 KB Output is correct
6 Correct 19 ms 7672 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 5980 KB Output is correct
2 Correct 23 ms 7772 KB Output is correct
3 Correct 23 ms 7760 KB Output is correct
4 Correct 39 ms 7828 KB Output is correct
5 Correct 38 ms 8020 KB Output is correct
6 Correct 19 ms 7672 KB Output is correct
7 Incorrect 16 ms 6748 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 18 ms 5980 KB Output is correct
2 Correct 44 ms 17748 KB Output is correct
3 Correct 42 ms 17744 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 5980 KB Output is correct
2 Correct 44 ms 17748 KB Output is correct
3 Correct 42 ms 17744 KB Output is correct
4 Incorrect 13 ms 5980 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 15 ms 5980 KB Output is correct
2 Correct 62 ms 26196 KB Output is correct
3 Correct 58 ms 26088 KB Output is correct
4 Correct 76 ms 25940 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 5980 KB Output is correct
2 Correct 62 ms 26196 KB Output is correct
3 Correct 58 ms 26088 KB Output is correct
4 Correct 76 ms 25940 KB Output is correct
5 Incorrect 15 ms 5976 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 15 ms 5940 KB Output is correct
2 Correct 67 ms 19840 KB Output is correct
3 Correct 79 ms 20052 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 5940 KB Output is correct
2 Correct 67 ms 19840 KB Output is correct
3 Correct 79 ms 20052 KB Output is correct
4 Incorrect 15 ms 6748 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 16 ms 5980 KB Output is correct
2 Correct 58 ms 26076 KB Output is correct
3 Correct 62 ms 26032 KB Output is correct
4 Correct 77 ms 26036 KB Output is correct
5 Correct 15 ms 5976 KB Output is correct
6 Correct 50 ms 19852 KB Output is correct
7 Correct 55 ms 19880 KB Output is correct
8 Correct 76 ms 21072 KB Output is correct
9 Correct 58 ms 20896 KB Output is correct
10 Correct 68 ms 23384 KB Output is correct
11 Correct 99 ms 22864 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5980 KB Output is correct
2 Correct 58 ms 26076 KB Output is correct
3 Correct 62 ms 26032 KB Output is correct
4 Correct 77 ms 26036 KB Output is correct
5 Correct 15 ms 5976 KB Output is correct
6 Correct 50 ms 19852 KB Output is correct
7 Correct 55 ms 19880 KB Output is correct
8 Correct 76 ms 21072 KB Output is correct
9 Correct 58 ms 20896 KB Output is correct
10 Correct 68 ms 23384 KB Output is correct
11 Correct 99 ms 22864 KB Output is correct
12 Incorrect 15 ms 6744 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 15 ms 5976 KB Output is correct
2 Correct 23 ms 7816 KB Output is correct
3 Correct 19 ms 7764 KB Output is correct
4 Correct 40 ms 7760 KB Output is correct
5 Correct 35 ms 8028 KB Output is correct
6 Correct 18 ms 7756 KB Output is correct
7 Correct 20 ms 6744 KB Output is correct
8 Correct 50 ms 20560 KB Output is correct
9 Correct 46 ms 20452 KB Output is correct
10 Correct 18 ms 6744 KB Output is correct
11 Correct 55 ms 29268 KB Output is correct
12 Correct 61 ms 29268 KB Output is correct
13 Correct 82 ms 29716 KB Output is correct
14 Correct 15 ms 6744 KB Output is correct
15 Correct 51 ms 19928 KB Output is correct
16 Correct 67 ms 20056 KB Output is correct
17 Correct 76 ms 21072 KB Output is correct
18 Correct 56 ms 21044 KB Output is correct
19 Correct 67 ms 23380 KB Output is correct
20 Correct 108 ms 22848 KB Output is correct
21 Correct 54 ms 21072 KB Output is correct
22 Correct 47 ms 21072 KB Output is correct
23 Correct 54 ms 21332 KB Output is correct
24 Correct 52 ms 21336 KB Output is correct
25 Correct 61 ms 23124 KB Output is correct
26 Correct 64 ms 20344 KB Output is correct
27 Correct 64 ms 20308 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 15 ms 5976 KB Output is correct
2 Correct 23 ms 7816 KB Output is correct
3 Correct 19 ms 7764 KB Output is correct
4 Correct 40 ms 7760 KB Output is correct
5 Correct 35 ms 8028 KB Output is correct
6 Correct 18 ms 7756 KB Output is correct
7 Correct 20 ms 6744 KB Output is correct
8 Correct 50 ms 20560 KB Output is correct
9 Correct 46 ms 20452 KB Output is correct
10 Correct 18 ms 6744 KB Output is correct
11 Correct 55 ms 29268 KB Output is correct
12 Correct 61 ms 29268 KB Output is correct
13 Correct 82 ms 29716 KB Output is correct
14 Correct 15 ms 6744 KB Output is correct
15 Correct 51 ms 19928 KB Output is correct
16 Correct 67 ms 20056 KB Output is correct
17 Correct 76 ms 21072 KB Output is correct
18 Correct 56 ms 21044 KB Output is correct
19 Correct 67 ms 23380 KB Output is correct
20 Correct 108 ms 22848 KB Output is correct
21 Correct 54 ms 21072 KB Output is correct
22 Correct 47 ms 21072 KB Output is correct
23 Correct 54 ms 21332 KB Output is correct
24 Correct 52 ms 21336 KB Output is correct
25 Correct 61 ms 23124 KB Output is correct
26 Correct 64 ms 20344 KB Output is correct
27 Correct 64 ms 20308 KB Output is correct
28 Incorrect 15 ms 6748 KB Extra information in the output file
29 Halted 0 ms 0 KB -