oj.uz

답안 #1042415

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1042415 2024-08-03T04:12:07 Z sleepntsheep Inside information (BOI21_servers) C
65 / 100
 3500 ms 29048 KB 
/* WHAT IS EXTRA INFORAMZTION GTR RR */

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

int max(int i, int j) { return i > j ? i : j; }
/*
 * 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)
 *
 * Should be able to optimize to O(N^1.5) using https://codeforces.com/blog/entry/71567?mobile=true&locale=en 
 */

#define N 120001
#define B 700

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;
    ua = anc(u, dd[a] + 1);
    va = anc(v, 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 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;

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

        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);
        }

    }
}

Compilation message

servers.c: In function 'pus_':
servers.c:32:26: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   32 |     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 22 ms 2136 KB Output is correct
2 Correct 49 ms 2644 KB Output is correct
3 Correct 59 ms 2724 KB Output is correct
4 Correct 57 ms 2644 KB Output is correct
5 Correct 70 ms 2820 KB Output is correct
6 Correct 29 ms 2640 KB Output is correct

Subtask #2
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 2136 KB Output is correct
2 Correct 49 ms 2644 KB Output is correct
3 Correct 59 ms 2724 KB Output is correct
4 Correct 57 ms 2644 KB Output is correct
5 Correct 70 ms 2820 KB Output is correct
6 Correct 29 ms 2640 KB Output is correct
7 Correct 23 ms 2048 KB Output is correct
8 Correct 113 ms 2640 KB Output is correct
9 Correct 65 ms 2832 KB Output is correct
10 Correct 266 ms 3220 KB Output is correct
11 Correct 138 ms 2916 KB Output is correct
12 Correct 49 ms 2644 KB Output is correct

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 2136 KB Output is correct
2 Correct 472 ms 17804 KB Output is correct
3 Correct 509 ms 17748 KB Output is correct

Subtask #4
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 2136 KB Output is correct
2 Correct 472 ms 17804 KB Output is correct
3 Correct 509 ms 17748 KB Output is correct
4 Correct 22 ms 2140 KB Output is correct
5 Correct 572 ms 18004 KB Output is correct
6 Correct 784 ms 18516 KB Output is correct
7 Correct 861 ms 18340 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 2136 KB Output is correct
2 Correct 993 ms 26144 KB Output is correct
3 Correct 1189 ms 26068 KB Output is correct
4 Correct 385 ms 26264 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 2136 KB Output is correct
2 Correct 993 ms 26144 KB Output is correct
3 Correct 1189 ms 26068 KB Output is correct
4 Correct 385 ms 26264 KB Output is correct
5 Correct 25 ms 2140 KB Output is correct
6 Execution timed out 3559 ms 26192 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 2132 KB Output is correct
2 Correct 322 ms 16676 KB Output is correct
3 Correct 1241 ms 16664 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 2132 KB Output is correct
2 Correct 322 ms 16676 KB Output is correct
3 Correct 1241 ms 16664 KB Output is correct
4 Correct 24 ms 2128 KB Output is correct
5 Correct 685 ms 16960 KB Output is correct
6 Correct 1973 ms 16936 KB Output is correct

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 2112 KB Output is correct
2 Correct 1232 ms 26192 KB Output is correct
3 Correct 1000 ms 27812 KB Output is correct
4 Correct 406 ms 27988 KB Output is correct
5 Correct 22 ms 2896 KB Output is correct
6 Correct 313 ms 18512 KB Output is correct
7 Correct 1130 ms 18448 KB Output is correct
8 Correct 1204 ms 19492 KB Output is correct
9 Correct 863 ms 19520 KB Output is correct
10 Correct 871 ms 22356 KB Output is correct
11 Correct 1086 ms 21280 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 2112 KB Output is correct
2 Correct 1232 ms 26192 KB Output is correct
3 Correct 1000 ms 27812 KB Output is correct
4 Correct 406 ms 27988 KB Output is correct
5 Correct 22 ms 2896 KB Output is correct
6 Correct 313 ms 18512 KB Output is correct
7 Correct 1130 ms 18448 KB Output is correct
8 Correct 1204 ms 19492 KB Output is correct
9 Correct 863 ms 19520 KB Output is correct
10 Correct 871 ms 22356 KB Output is correct
11 Correct 1086 ms 21280 KB Output is correct
12 Correct 25 ms 3412 KB Output is correct
13 Execution timed out 3566 ms 28028 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 2908 KB Output is correct
2 Correct 42 ms 3668 KB Output is correct
3 Correct 32 ms 3624 KB Output is correct
4 Correct 65 ms 3724 KB Output is correct
5 Correct 59 ms 4020 KB Output is correct
6 Correct 31 ms 3676 KB Output is correct
7 Correct 22 ms 2908 KB Output is correct
8 Correct 515 ms 19664 KB Output is correct
9 Correct 518 ms 19468 KB Output is correct
10 Correct 23 ms 2896 KB Output is correct
11 Correct 1247 ms 27980 KB Output is correct
12 Correct 1126 ms 27892 KB Output is correct
13 Correct 406 ms 28008 KB Output is correct
14 Correct 24 ms 3412 KB Output is correct
15 Correct 335 ms 18492 KB Output is correct
16 Correct 1426 ms 18444 KB Output is correct
17 Correct 1560 ms 19588 KB Output is correct
18 Correct 1177 ms 19428 KB Output is correct
19 Correct 1000 ms 22332 KB Output is correct
20 Correct 1159 ms 21344 KB Output is correct
21 Correct 498 ms 19592 KB Output is correct
22 Correct 535 ms 19780 KB Output is correct
23 Correct 668 ms 19796 KB Output is correct
24 Correct 595 ms 19796 KB Output is correct
25 Correct 962 ms 21844 KB Output is correct
26 Correct 1815 ms 16936 KB Output is correct
27 Correct 1647 ms 18948 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 2908 KB Output is correct
2 Correct 42 ms 3668 KB Output is correct
3 Correct 32 ms 3624 KB Output is correct
4 Correct 65 ms 3724 KB Output is correct
5 Correct 59 ms 4020 KB Output is correct
6 Correct 31 ms 3676 KB Output is correct
7 Correct 22 ms 2908 KB Output is correct
8 Correct 515 ms 19664 KB Output is correct
9 Correct 518 ms 19468 KB Output is correct
10 Correct 23 ms 2896 KB Output is correct
11 Correct 1247 ms 27980 KB Output is correct
12 Correct 1126 ms 27892 KB Output is correct
13 Correct 406 ms 28008 KB Output is correct
14 Correct 24 ms 3412 KB Output is correct
15 Correct 335 ms 18492 KB Output is correct
16 Correct 1426 ms 18444 KB Output is correct
17 Correct 1560 ms 19588 KB Output is correct
18 Correct 1177 ms 19428 KB Output is correct
19 Correct 1000 ms 22332 KB Output is correct
20 Correct 1159 ms 21344 KB Output is correct
21 Correct 498 ms 19592 KB Output is correct
22 Correct 535 ms 19780 KB Output is correct
23 Correct 668 ms 19796 KB Output is correct
24 Correct 595 ms 19796 KB Output is correct
25 Correct 962 ms 21844 KB Output is correct
26 Correct 1815 ms 16936 KB Output is correct
27 Correct 1647 ms 18948 KB Output is correct
28 Correct 47 ms 3412 KB Output is correct
29 Correct 105 ms 3408 KB Output is correct
30 Correct 58 ms 3824 KB Output is correct
31 Correct 240 ms 3868 KB Output is correct
32 Correct 146 ms 3924 KB Output is correct
33 Correct 48 ms 3920 KB Output is correct
34 Correct 30 ms 4944 KB Output is correct
35 Correct 683 ms 20844 KB Output is correct
36 Correct 715 ms 20036 KB Output is correct
37 Correct 786 ms 20052 KB Output is correct
38 Correct 34 ms 3080 KB Output is correct
39 Execution timed out 3560 ms 29048 KB Time limit exceeded
40 Halted 0 ms 0 KB -