oj.uz

답안 #1042397

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1042397 2024-08-03T03:45:19 Z sleepntsheep Inside information (BOI21_servers) C
50 / 100
 3406 ms 26328 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')
            puts(query_yesno(qq[i].b, qq[i].a, j - 1) ? "yes": "no");
        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 31 ms 2652 KB Output is correct
2 Correct 58 ms 2616 KB Output is correct
3 Correct 46 ms 2652 KB Output is correct
4 Correct 77 ms 2732 KB Output is correct
5 Correct 86 ms 2900 KB Output is correct
6 Correct 50 ms 2644 KB Output is correct

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 2652 KB Output is correct
2 Correct 58 ms 2616 KB Output is correct
3 Correct 46 ms 2652 KB Output is correct
4 Correct 77 ms 2732 KB Output is correct
5 Correct 86 ms 2900 KB Output is correct
6 Correct 50 ms 2644 KB Output is correct
7 Correct 29 ms 2648 KB Output is correct
8 Incorrect 84 ms 2560 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 2140 KB Output is correct
2 Correct 927 ms 17676 KB Output is correct
3 Correct 925 ms 17660 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 2140 KB Output is correct
2 Correct 927 ms 17676 KB Output is correct
3 Correct 925 ms 17660 KB Output is correct
4 Correct 28 ms 2648 KB Output is correct
5 Incorrect 998 ms 18156 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 2136 KB Output is correct
2 Correct 1774 ms 26180 KB Output is correct
3 Correct 1697 ms 26164 KB Output is correct
4 Correct 737 ms 25992 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 2136 KB Output is correct
2 Correct 1774 ms 26180 KB Output is correct
3 Correct 1697 ms 26164 KB Output is correct
4 Correct 737 ms 25992 KB Output is correct
5 Correct 44 ms 2648 KB Output is correct
6 Incorrect 3371 ms 26328 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 2164 KB Output is correct
2 Correct 665 ms 16772 KB Output is correct
3 Correct 2019 ms 16620 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 2164 KB Output is correct
2 Correct 665 ms 16772 KB Output is correct
3 Correct 2019 ms 16620 KB Output is correct
4 Correct 29 ms 2140 KB Output is correct
5 Incorrect 742 ms 16888 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 2648 KB Output is correct
2 Correct 1704 ms 26192 KB Output is correct
3 Correct 1689 ms 26192 KB Output is correct
4 Correct 681 ms 26140 KB Output is correct
5 Correct 30 ms 2648 KB Output is correct
6 Correct 603 ms 16724 KB Output is correct
7 Correct 1934 ms 16620 KB Output is correct
8 Correct 2454 ms 17672 KB Output is correct
9 Correct 1937 ms 17792 KB Output is correct
10 Correct 1890 ms 20156 KB Output is correct
11 Correct 2284 ms 19472 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 2648 KB Output is correct
2 Correct 1704 ms 26192 KB Output is correct
3 Correct 1689 ms 26192 KB Output is correct
4 Correct 681 ms 26140 KB Output is correct
5 Correct 30 ms 2648 KB Output is correct
6 Correct 603 ms 16724 KB Output is correct
7 Correct 1934 ms 16620 KB Output is correct
8 Correct 2454 ms 17672 KB Output is correct
9 Correct 1937 ms 17792 KB Output is correct
10 Correct 1890 ms 20156 KB Output is correct
11 Correct 2284 ms 19472 KB Output is correct
12 Correct 30 ms 2652 KB Output is correct
13 Incorrect 3406 ms 26324 KB Extra information in the output file
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 2128 KB Output is correct
2 Correct 61 ms 2644 KB Output is correct
3 Correct 47 ms 5212 KB Output is correct
4 Correct 90 ms 2648 KB Output is correct
5 Correct 107 ms 2896 KB Output is correct
6 Correct 53 ms 2764 KB Output is correct
7 Correct 28 ms 2908 KB Output is correct
8 Correct 1008 ms 17864 KB Output is correct
9 Correct 987 ms 17668 KB Output is correct
10 Correct 44 ms 2136 KB Output is correct
11 Correct 2011 ms 26140 KB Output is correct
12 Correct 1925 ms 26192 KB Output is correct
13 Correct 715 ms 26160 KB Output is correct
14 Correct 29 ms 2652 KB Output is correct
15 Correct 670 ms 17012 KB Output is correct
16 Correct 2027 ms 16704 KB Output is correct
17 Correct 2396 ms 17604 KB Output is correct
18 Correct 1923 ms 17748 KB Output is correct
19 Correct 1841 ms 20572 KB Output is correct
20 Correct 2215 ms 19556 KB Output is correct
21 Correct 918 ms 17500 KB Output is correct
22 Correct 951 ms 18016 KB Output is correct
23 Correct 1228 ms 18428 KB Output is correct
24 Correct 1137 ms 18004 KB Output is correct
25 Correct 1901 ms 19792 KB Output is correct
26 Correct 2983 ms 17100 KB Output is correct
27 Correct 3056 ms 16976 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 2128 KB Output is correct
2 Correct 61 ms 2644 KB Output is correct
3 Correct 47 ms 5212 KB Output is correct
4 Correct 90 ms 2648 KB Output is correct
5 Correct 107 ms 2896 KB Output is correct
6 Correct 53 ms 2764 KB Output is correct
7 Correct 28 ms 2908 KB Output is correct
8 Correct 1008 ms 17864 KB Output is correct
9 Correct 987 ms 17668 KB Output is correct
10 Correct 44 ms 2136 KB Output is correct
11 Correct 2011 ms 26140 KB Output is correct
12 Correct 1925 ms 26192 KB Output is correct
13 Correct 715 ms 26160 KB Output is correct
14 Correct 29 ms 2652 KB Output is correct
15 Correct 670 ms 17012 KB Output is correct
16 Correct 2027 ms 16704 KB Output is correct
17 Correct 2396 ms 17604 KB Output is correct
18 Correct 1923 ms 17748 KB Output is correct
19 Correct 1841 ms 20572 KB Output is correct
20 Correct 2215 ms 19556 KB Output is correct
21 Correct 918 ms 17500 KB Output is correct
22 Correct 951 ms 18016 KB Output is correct
23 Correct 1228 ms 18428 KB Output is correct
24 Correct 1137 ms 18004 KB Output is correct
25 Correct 1901 ms 19792 KB Output is correct
26 Correct 2983 ms 17100 KB Output is correct
27 Correct 3056 ms 16976 KB Output is correct
28 Correct 29 ms 2652 KB Output is correct
29 Incorrect 90 ms 2520 KB Extra information in the output file
30 Halted 0 ms 0 KB -