oj.uz

답안 #1042416

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1042416 2024-08-03T04:12:38 Z sleepntsheep Inside information (BOI21_servers) C
20 / 100
 3500 ms 28064 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 200

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 38 ms 2952 KB Output is correct
2 Correct 77 ms 3664 KB Output is correct
3 Correct 111 ms 3844 KB Output is correct
4 Correct 105 ms 3664 KB Output is correct
5 Correct 115 ms 3960 KB Output is correct
6 Correct 54 ms 4184 KB Output is correct

Subtask #2
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 2952 KB Output is correct
2 Correct 77 ms 3664 KB Output is correct
3 Correct 111 ms 3844 KB Output is correct
4 Correct 105 ms 3664 KB Output is correct
5 Correct 115 ms 3960 KB Output is correct
6 Correct 54 ms 4184 KB Output is correct
7 Correct 37 ms 2896 KB Output is correct
8 Correct 93 ms 3428 KB Output is correct
9 Correct 69 ms 3412 KB Output is correct
10 Correct 146 ms 3412 KB Output is correct
11 Correct 118 ms 3672 KB Output is correct
12 Correct 65 ms 3416 KB Output is correct

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 2992 KB Output is correct
2 Correct 1651 ms 19348 KB Output is correct
3 Correct 1438 ms 19456 KB Output is correct

Subtask #4
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 2992 KB Output is correct
2 Correct 1651 ms 19348 KB Output is correct
3 Correct 1438 ms 19456 KB Output is correct
4 Correct 68 ms 2776 KB Output is correct
5 Correct 1748 ms 19640 KB Output is correct
6 Correct 1573 ms 19580 KB Output is correct
7 Correct 1587 ms 19536 KB Output is correct

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 2896 KB Output is correct
2 Correct 3301 ms 27792 KB Output is correct
3 Execution timed out 3582 ms 28064 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 2896 KB Output is correct
2 Correct 3301 ms 27792 KB Output is correct
3 Execution timed out 3582 ms 28064 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 3420 KB Output is correct
2 Correct 981 ms 18660 KB Output is correct
3 Correct 3442 ms 18440 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 3420 KB Output is correct
2 Correct 981 ms 18660 KB Output is correct
3 Correct 3442 ms 18440 KB Output is correct
4 Correct 39 ms 3416 KB Output is correct
5 Correct 1074 ms 18856 KB Output is correct
6 Execution timed out 3564 ms 18696 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 3420 KB Output is correct
2 Correct 2583 ms 27912 KB Output is correct
3 Correct 2551 ms 26168 KB Output is correct
4 Correct 1035 ms 25940 KB Output is correct
5 Correct 35 ms 2648 KB Output is correct
6 Correct 911 ms 16724 KB Output is correct
7 Correct 2778 ms 16720 KB Output is correct
8 Execution timed out 3519 ms 17736 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 3420 KB Output is correct
2 Correct 2583 ms 27912 KB Output is correct
3 Correct 2551 ms 26168 KB Output is correct
4 Correct 1035 ms 25940 KB Output is correct
5 Correct 35 ms 2648 KB Output is correct
6 Correct 911 ms 16724 KB Output is correct
7 Correct 2778 ms 16720 KB Output is correct
8 Execution timed out 3519 ms 17736 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 2652 KB Output is correct
2 Correct 82 ms 2544 KB Output is correct
3 Correct 61 ms 2772 KB Output is correct
4 Correct 92 ms 2652 KB Output is correct
5 Correct 102 ms 3408 KB Output is correct
6 Correct 56 ms 2644 KB Output is correct
7 Correct 35 ms 2264 KB Output is correct
8 Correct 1419 ms 17648 KB Output is correct
9 Correct 1422 ms 17676 KB Output is correct
10 Correct 37 ms 2136 KB Output is correct
11 Correct 2615 ms 26192 KB Output is correct
12 Correct 2494 ms 28064 KB Output is correct
13 Correct 1004 ms 27992 KB Output is correct
14 Correct 36 ms 3372 KB Output is correct
15 Correct 914 ms 18732 KB Output is correct
16 Correct 2898 ms 18780 KB Output is correct
17 Execution timed out 3570 ms 19816 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 2652 KB Output is correct
2 Correct 82 ms 2544 KB Output is correct
3 Correct 61 ms 2772 KB Output is correct
4 Correct 92 ms 2652 KB Output is correct
5 Correct 102 ms 3408 KB Output is correct
6 Correct 56 ms 2644 KB Output is correct
7 Correct 35 ms 2264 KB Output is correct
8 Correct 1419 ms 17648 KB Output is correct
9 Correct 1422 ms 17676 KB Output is correct
10 Correct 37 ms 2136 KB Output is correct
11 Correct 2615 ms 26192 KB Output is correct
12 Correct 2494 ms 28064 KB Output is correct
13 Correct 1004 ms 27992 KB Output is correct
14 Correct 36 ms 3372 KB Output is correct
15 Correct 914 ms 18732 KB Output is correct
16 Correct 2898 ms 18780 KB Output is correct
17 Execution timed out 3570 ms 19816 KB Time limit exceeded
18 Halted 0 ms 0 KB -