oj.uz

답안 #1042444

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1042444 2024-08-03T04:33:35 Z sleepntsheep Inside information (BOI21_servers) C
62.5 / 100
 3500 ms 25428 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 900

int n, q, pp[N], jj[N], dd[N], up[N], temp, inc[N], tin[N], tout[N], timer;

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) {
    tin[u] = timer++;
    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);
    }
    tout[u] = timer - 1;

    for (int j = 0; j < eo[u]; ++j) if (eh[u][j] == p) {
        int ww = fh[u][j];
        for (int k = j + 1; k < eo[u]; ++k)
            eh[u][k - 1] = eh[u][k], fh[u][k - 1] = fh[u][k];
        --eo[u];
        eh[u][eo[u]] = p;
        fh[u][eo[u]] = ww;
        break;
    }
}

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];

int navigate(int u, int v) {
    int lb = -1, ub = eo[u],z=v;
    while (ub-lb>1){
        int md=lb+(ub-lb)/2;
        if(tin[eh[u][md]]<=tin[v])lb=md,z=eh[u][md];
        else ub=md;
    }
    return z;
}

/* 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 = navigate(a, v);
        return inc[v] - inc[va] == dd[v] - dd[va] && up[v] <= time;
    }
    if (v == a) {
        ua = navigate(a, u);
        return inc[u] - inc[ua] == 0 && up[ua] <= time;
    }

    va = navigate(a, v);
    ua = navigate(a, u);
    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;
    int ee = u > 1 ? eo[u] : eo[u]-1;
    for (int j = 0; j <= ee; ++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 = 1; i <= n; ++i)
        if (comp[i] == -1)
            efs(i, tme, i);

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

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:154:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |     scanf("%d%d", &n, &q);
      |     ^~~~~~~~~~~~~~~~~~~~~
servers.c:161:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |         scanf(" %s%d", s, &a);
      |         ^~~~~~~~~~~~~~~~~~~~~
servers.c:163:13: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |             scanf("%d", &b);
      |             ^~~~~~~~~~~~~~~
servers.c:166:13: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |             scanf("%d", &b);
      |             ^~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 6748 KB Output is correct
2 Correct 45 ms 7252 KB Output is correct
3 Correct 36 ms 7256 KB Output is correct
4 Correct 43 ms 7252 KB Output is correct
5 Correct 46 ms 7508 KB Output is correct
6 Correct 37 ms 7252 KB Output is correct

Subtask #2
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 6748 KB Output is correct
2 Correct 45 ms 7252 KB Output is correct
3 Correct 36 ms 7256 KB Output is correct
4 Correct 43 ms 7252 KB Output is correct
5 Correct 46 ms 7508 KB Output is correct
6 Correct 37 ms 7252 KB Output is correct
7 Correct 22 ms 6744 KB Output is correct
8 Correct 114 ms 7108 KB Output is correct
9 Correct 92 ms 7248 KB Output is correct
10 Correct 190 ms 7252 KB Output is correct
11 Correct 109 ms 7248 KB Output is correct
12 Correct 137 ms 7352 KB Output is correct

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 6748 KB Output is correct
2 Correct 389 ms 18812 KB Output is correct
3 Correct 371 ms 18516 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 6748 KB Output is correct
2 Correct 389 ms 18812 KB Output is correct
3 Correct 371 ms 18516 KB Output is correct
4 Correct 25 ms 6748 KB Output is correct
5 Correct 1299 ms 19028 KB Output is correct
6 Correct 2393 ms 19452 KB Output is correct
7 Execution timed out 3559 ms 19028 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 6748 KB Output is correct
2 Correct 560 ms 25240 KB Output is correct
3 Correct 551 ms 25172 KB Output is correct
4 Correct 286 ms 25168 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 6748 KB Output is correct
2 Correct 560 ms 25240 KB Output is correct
3 Correct 551 ms 25172 KB Output is correct
4 Correct 286 ms 25168 KB Output is correct
5 Correct 26 ms 6748 KB Output is correct
6 Execution timed out 3543 ms 25428 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 6744 KB Output is correct
2 Correct 239 ms 17616 KB Output is correct
3 Correct 611 ms 17568 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 6744 KB Output is correct
2 Correct 239 ms 17616 KB Output is correct
3 Correct 611 ms 17568 KB Output is correct
4 Correct 23 ms 6744 KB Output is correct
5 Correct 550 ms 18120 KB Output is correct
6 Correct 1160 ms 18000 KB Output is correct

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 6744 KB Output is correct
2 Correct 570 ms 25168 KB Output is correct
3 Correct 591 ms 25224 KB Output is correct
4 Correct 292 ms 25168 KB Output is correct
5 Correct 25 ms 6840 KB Output is correct
6 Correct 231 ms 17492 KB Output is correct
7 Correct 629 ms 17748 KB Output is correct
8 Correct 752 ms 18512 KB Output is correct
9 Correct 621 ms 18516 KB Output is correct
10 Correct 621 ms 20304 KB Output is correct
11 Correct 729 ms 19932 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 6744 KB Output is correct
2 Correct 570 ms 25168 KB Output is correct
3 Correct 591 ms 25224 KB Output is correct
4 Correct 292 ms 25168 KB Output is correct
5 Correct 25 ms 6840 KB Output is correct
6 Correct 231 ms 17492 KB Output is correct
7 Correct 629 ms 17748 KB Output is correct
8 Correct 752 ms 18512 KB Output is correct
9 Correct 621 ms 18516 KB Output is correct
10 Correct 621 ms 20304 KB Output is correct
11 Correct 729 ms 19932 KB Output is correct
12 Correct 21 ms 6744 KB Output is correct
13 Execution timed out 3552 ms 25424 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 6748 KB Output is correct
2 Correct 36 ms 7168 KB Output is correct
3 Correct 43 ms 7236 KB Output is correct
4 Correct 43 ms 7148 KB Output is correct
5 Correct 41 ms 7396 KB Output is correct
6 Correct 45 ms 7248 KB Output is correct
7 Correct 23 ms 7004 KB Output is correct
8 Correct 358 ms 18868 KB Output is correct
9 Correct 356 ms 18516 KB Output is correct
10 Correct 21 ms 6744 KB Output is correct
11 Correct 585 ms 25084 KB Output is correct
12 Correct 559 ms 25172 KB Output is correct
13 Correct 280 ms 25172 KB Output is correct
14 Correct 20 ms 6748 KB Output is correct
15 Correct 232 ms 17536 KB Output is correct
16 Correct 586 ms 17532 KB Output is correct
17 Correct 787 ms 18632 KB Output is correct
18 Correct 623 ms 18768 KB Output is correct
19 Correct 611 ms 20596 KB Output is correct
20 Correct 738 ms 19792 KB Output is correct
21 Correct 380 ms 18544 KB Output is correct
22 Correct 391 ms 18808 KB Output is correct
23 Correct 395 ms 18996 KB Output is correct
24 Correct 404 ms 18984 KB Output is correct
25 Correct 613 ms 20164 KB Output is correct
26 Correct 1002 ms 18008 KB Output is correct
27 Correct 957 ms 18012 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 6748 KB Output is correct
2 Correct 36 ms 7168 KB Output is correct
3 Correct 43 ms 7236 KB Output is correct
4 Correct 43 ms 7148 KB Output is correct
5 Correct 41 ms 7396 KB Output is correct
6 Correct 45 ms 7248 KB Output is correct
7 Correct 23 ms 7004 KB Output is correct
8 Correct 358 ms 18868 KB Output is correct
9 Correct 356 ms 18516 KB Output is correct
10 Correct 21 ms 6744 KB Output is correct
11 Correct 585 ms 25084 KB Output is correct
12 Correct 559 ms 25172 KB Output is correct
13 Correct 280 ms 25172 KB Output is correct
14 Correct 20 ms 6748 KB Output is correct
15 Correct 232 ms 17536 KB Output is correct
16 Correct 586 ms 17532 KB Output is correct
17 Correct 787 ms 18632 KB Output is correct
18 Correct 623 ms 18768 KB Output is correct
19 Correct 611 ms 20596 KB Output is correct
20 Correct 738 ms 19792 KB Output is correct
21 Correct 380 ms 18544 KB Output is correct
22 Correct 391 ms 18808 KB Output is correct
23 Correct 395 ms 18996 KB Output is correct
24 Correct 404 ms 18984 KB Output is correct
25 Correct 613 ms 20164 KB Output is correct
26 Correct 1002 ms 18008 KB Output is correct
27 Correct 957 ms 18012 KB Output is correct
28 Correct 22 ms 6748 KB Output is correct
29 Correct 116 ms 7240 KB Output is correct
30 Correct 84 ms 7228 KB Output is correct
31 Correct 195 ms 7248 KB Output is correct
32 Correct 109 ms 7448 KB Output is correct
33 Correct 125 ms 7248 KB Output is correct
34 Correct 24 ms 7000 KB Output is correct
35 Correct 1238 ms 18996 KB Output is correct
36 Correct 2428 ms 19456 KB Output is correct
37 Execution timed out 3562 ms 19176 KB Time limit exceeded
38 Halted 0 ms 0 KB -