oj.uz

답안 #1042370

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1042370 2024-08-03T02:55:42 Z sleepntsheep Inside information (BOI21_servers) C
7.5 / 100
 89 ms 29520 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]) && (dd[u] - dd[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
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 6748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 6748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 6744 KB Output is correct
2 Correct 48 ms 20384 KB Output is correct
3 Correct 47 ms 20564 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 6744 KB Output is correct
2 Correct 48 ms 20384 KB Output is correct
3 Correct 47 ms 20564 KB Output is correct
4 Incorrect 14 ms 6748 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 6740 KB Output is correct
2 Correct 70 ms 29268 KB Output is correct
3 Correct 57 ms 29520 KB Output is correct
4 Correct 89 ms 29268 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 6740 KB Output is correct
2 Correct 70 ms 29268 KB Output is correct
3 Correct 57 ms 29520 KB Output is correct
4 Correct 89 ms 29268 KB Output is correct
5 Incorrect 16 ms 6748 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 6744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 6744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 6744 KB Output is correct
2 Correct 57 ms 29516 KB Output is correct
3 Correct 59 ms 29520 KB Output is correct
4 Correct 78 ms 29264 KB Output is correct
5 Incorrect 15 ms 6748 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 6744 KB Output is correct
2 Correct 57 ms 29516 KB Output is correct
3 Correct 59 ms 29520 KB Output is correct
4 Correct 78 ms 29264 KB Output is correct
5 Incorrect 15 ms 6748 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 20 ms 6744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 20 ms 6744 KB Output isn't correct
2 Halted 0 ms 0 KB -