oj.uz

답안 #1042400

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1042400 2024-08-03T03:46:43 Z sleepntsheep Inside information (BOI21_servers) C
32.5 / 100
 3500 ms 26384 KB 
/* WHAT IS EXTRA INFORAMZTION GTR RR */

#include <stdio.h>
#include <stdlib.h>

/*
 * For "Q" queries, use LCA + prefix sum on tree ~ 3O(lgn) [for finding lca and almost-lca]
 *
 * Every B queries of any type, do naive dp on tree (reverse edge order)
 * to find answer for "C" queries  ~ O(n)
 *
 * On "C" queries, use cached answer from above and count all edges that appeared after that (by "Q")
 * ~ O(B lgn)
 *
 *
 * Time complexity = O(N^2 / B) + O(N lgn) + O(N B lgn)
 *
 * Let B = sqrt(N / lgN)
 */

#define N 120001
#define B 300

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[2];
    int a, b;
} 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, ua;

    if (u == a) {
        va = anc(v, dd[a] + 1);
        return inc[v] - inc[va] == dd[v] - dd[va] && up[v] <= time;
    }
    if (v == a) {
        ua = anc(u, dd[a] + 1);
        return inc[u] - inc[ua] == 0 && up[ua] <= time;
    }
    ua = anc(u, dd[a] + 1);
    va = anc(v, dd[a] + 1);

    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 time, int root) {
    comp[u] = root;
    for (int j = 0; j < eo[u]; ++j)
        if (fh[u][j] <= time && comp[eh[u][j]] == -1)
            efs(eh[u][j], 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[0] != '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, 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) {
        int a, b = 0;
        char *s = qq[i].type;

        scanf(" %s%d", s, &a);
        if (s[0] == 'S') {
            scanf("%d", &b);
            link(a, b, j++);
        } else if (s[0] == 'Q')
            scanf("%d", &b);

        qq[i].a = a, qq[i].b = 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[0] == 'S')
            ++j;
        else if (qq[i].type[0] == 'Q')
            printf(query_yesno(qq[i].b, qq[i].a, j - 1) ? "yes\n": "no\n");
        else if (qq[i].type[0] == 'C') {
            int focus = qq[i].a;
            int addition = 0;
            for (int k = at; k < i; ++k)
                if (qq[k].type[0] == '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);
        }

        if (i % B == 0) {
            build(i, j);
            at = i + 1;
        }
    }
}

Compilation message

servers.c: In function 'pus_':
servers.c:29:26: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   29 |     else if (0 == (o & o - 1)) eh[i] = (int*)realloc(eh[i], 2 * o * sizeof **eh);
      |                        ~~^~~
servers.c: In function 'main':
servers.c:130:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |     scanf("%d%d", &n, &q);
      |     ^~~~~~~~~~~~~~~~~~~~~
servers.c:137:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |         scanf(" %s%d", s, &a);
      |         ^~~~~~~~~~~~~~~~~~~~~
servers.c:139:13: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |             scanf("%d", &b);
      |             ^~~~~~~~~~~~~~~
servers.c:142:13: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |             scanf("%d", &b);
      |             ^~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 2652 KB Output is correct
2 Correct 61 ms 2640 KB Output is correct
3 Correct 47 ms 3408 KB Output is correct
4 Correct 76 ms 3160 KB Output is correct
5 Correct 80 ms 2948 KB Output is correct
6 Correct 44 ms 2640 KB Output is correct

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 2652 KB Output is correct
2 Correct 61 ms 2640 KB Output is correct
3 Correct 47 ms 3408 KB Output is correct
4 Correct 76 ms 3160 KB Output is correct
5 Correct 80 ms 2948 KB Output is correct
6 Correct 44 ms 2640 KB Output is correct
7 Correct 30 ms 2392 KB Output is correct
8 Incorrect 89 ms 2676 KB Extra information in the output file
9 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 2896 KB Output is correct
2 Correct 982 ms 17744 KB Output is correct
3 Correct 985 ms 17748 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 2896 KB Output is correct
2 Correct 982 ms 17744 KB Output is correct
3 Correct 985 ms 17748 KB Output is correct
4 Correct 29 ms 2760 KB Output is correct
5 Incorrect 1022 ms 18000 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 2132 KB Output is correct
2 Correct 1785 ms 26104 KB Output is correct
3 Correct 1701 ms 26092 KB Output is correct
4 Correct 691 ms 26192 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 2132 KB Output is correct
2 Correct 1785 ms 26104 KB Output is correct
3 Correct 1701 ms 26092 KB Output is correct
4 Correct 691 ms 26192 KB Output is correct
5 Correct 31 ms 2648 KB Output is correct
6 Incorrect 3413 ms 26220 KB Extra information in the output file
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 2204 KB Output is correct
2 Correct 632 ms 16628 KB Output is correct
3 Correct 2041 ms 16624 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 2204 KB Output is correct
2 Correct 632 ms 16628 KB Output is correct
3 Correct 2041 ms 16624 KB Output is correct
4 Correct 34 ms 2652 KB Output is correct
5 Incorrect 754 ms 16988 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 2652 KB Output is correct
2 Correct 1739 ms 26192 KB Output is correct
3 Correct 1864 ms 26216 KB Output is correct
4 Correct 742 ms 26196 KB Output is correct
5 Correct 30 ms 2652 KB Output is correct
6 Correct 699 ms 16724 KB Output is correct
7 Correct 1953 ms 16616 KB Output is correct
8 Correct 2390 ms 17696 KB Output is correct
9 Correct 1908 ms 17720 KB Output is correct
10 Correct 1814 ms 20224 KB Output is correct
11 Correct 2437 ms 19532 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 2652 KB Output is correct
2 Correct 1739 ms 26192 KB Output is correct
3 Correct 1864 ms 26216 KB Output is correct
4 Correct 742 ms 26196 KB Output is correct
5 Correct 30 ms 2652 KB Output is correct
6 Correct 699 ms 16724 KB Output is correct
7 Correct 1953 ms 16616 KB Output is correct
8 Correct 2390 ms 17696 KB Output is correct
9 Correct 1908 ms 17720 KB Output is correct
10 Correct 1814 ms 20224 KB Output is correct
11 Correct 2437 ms 19532 KB Output is correct
12 Correct 60 ms 2828 KB Output is correct
13 Execution timed out 3541 ms 26280 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 2140 KB Output is correct
2 Correct 59 ms 2644 KB Output is correct
3 Correct 48 ms 3408 KB Output is correct
4 Correct 111 ms 2644 KB Output is correct
5 Correct 86 ms 3592 KB Output is correct
6 Correct 49 ms 2640 KB Output is correct
7 Correct 29 ms 2140 KB Output is correct
8 Correct 1004 ms 17748 KB Output is correct
9 Correct 1016 ms 17688 KB Output is correct
10 Correct 32 ms 2760 KB Output is correct
11 Correct 1990 ms 26384 KB Output is correct
12 Correct 2274 ms 26196 KB Output is correct
13 Correct 799 ms 26096 KB Output is correct
14 Correct 29 ms 2648 KB Output is correct
15 Correct 684 ms 16780 KB Output is correct
16 Correct 2425 ms 16788 KB Output is correct
17 Correct 2972 ms 17712 KB Output is correct
18 Correct 2356 ms 17632 KB Output is correct
19 Correct 2011 ms 20044 KB Output is correct
20 Correct 2401 ms 19540 KB Output is correct
21 Correct 1076 ms 17748 KB Output is correct
22 Correct 1173 ms 17748 KB Output is correct
23 Correct 1502 ms 18112 KB Output is correct
24 Correct 1577 ms 18196 KB Output is correct
25 Correct 2097 ms 19796 KB Output is correct
26 Execution timed out 3558 ms 16976 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 2140 KB Output is correct
2 Correct 59 ms 2644 KB Output is correct
3 Correct 48 ms 3408 KB Output is correct
4 Correct 111 ms 2644 KB Output is correct
5 Correct 86 ms 3592 KB Output is correct
6 Correct 49 ms 2640 KB Output is correct
7 Correct 29 ms 2140 KB Output is correct
8 Correct 1004 ms 17748 KB Output is correct
9 Correct 1016 ms 17688 KB Output is correct
10 Correct 32 ms 2760 KB Output is correct
11 Correct 1990 ms 26384 KB Output is correct
12 Correct 2274 ms 26196 KB Output is correct
13 Correct 799 ms 26096 KB Output is correct
14 Correct 29 ms 2648 KB Output is correct
15 Correct 684 ms 16780 KB Output is correct
16 Correct 2425 ms 16788 KB Output is correct
17 Correct 2972 ms 17712 KB Output is correct
18 Correct 2356 ms 17632 KB Output is correct
19 Correct 2011 ms 20044 KB Output is correct
20 Correct 2401 ms 19540 KB Output is correct
21 Correct 1076 ms 17748 KB Output is correct
22 Correct 1173 ms 17748 KB Output is correct
23 Correct 1502 ms 18112 KB Output is correct
24 Correct 1577 ms 18196 KB Output is correct
25 Correct 2097 ms 19796 KB Output is correct
26 Execution timed out 3558 ms 16976 KB Time limit exceeded
27 Halted 0 ms 0 KB -