oj.uz

Submission #1042417

# Submission time Handle Problem Language Result Execution time Memory
1042417 2024-08-03T04:13:44 Z sleepntsheep Inside information (BOI21_servers) C
65 / 100
 3500 ms 28752 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 1200

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

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3416 KB Output is correct
2 Correct 36 ms 4236 KB Output is correct
3 Correct 28 ms 3932 KB Output is correct
4 Correct 49 ms 3768 KB Output is correct
5 Correct 48 ms 4160 KB Output is correct
6 Correct 26 ms 3924 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3416 KB Output is correct
2 Correct 36 ms 4236 KB Output is correct
3 Correct 28 ms 3932 KB Output is correct
4 Correct 49 ms 3768 KB Output is correct
5 Correct 48 ms 4160 KB Output is correct
6 Correct 26 ms 3924 KB Output is correct
7 Correct 22 ms 2652 KB Output is correct
8 Correct 139 ms 3320 KB Output is correct
9 Correct 72 ms 3664 KB Output is correct
10 Correct 358 ms 3540 KB Output is correct
11 Correct 200 ms 3796 KB Output is correct
12 Correct 59 ms 3628 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 2896 KB Output is correct
2 Correct 277 ms 19388 KB Output is correct
3 Correct 276 ms 19316 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 2896 KB Output is correct
2 Correct 277 ms 19388 KB Output is correct
3 Correct 276 ms 19316 KB Output is correct
4 Correct 23 ms 2644 KB Output is correct
5 Correct 388 ms 19796 KB Output is correct
6 Correct 641 ms 19624 KB Output is correct
7 Correct 776 ms 19424 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3512 KB Output is correct
2 Correct 494 ms 28324 KB Output is correct
3 Correct 513 ms 28240 KB Output is correct
4 Correct 245 ms 28752 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3512 KB Output is correct
2 Correct 494 ms 28324 KB Output is correct
3 Correct 513 ms 28240 KB Output is correct
4 Correct 245 ms 28752 KB Output is correct
5 Correct 22 ms 2908 KB Output is correct
6 Execution timed out 3544 ms 28648 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3412 KB Output is correct
2 Correct 202 ms 18800 KB Output is correct
3 Correct 521 ms 18644 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3412 KB Output is correct
2 Correct 202 ms 18800 KB Output is correct
3 Correct 521 ms 18644 KB Output is correct
4 Correct 21 ms 3420 KB Output is correct
5 Correct 740 ms 18964 KB Output is correct
6 Correct 1592 ms 19008 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2652 KB Output is correct
2 Correct 476 ms 28240 KB Output is correct
3 Correct 506 ms 28028 KB Output is correct
4 Correct 243 ms 28192 KB Output is correct
5 Correct 20 ms 2648 KB Output is correct
6 Correct 195 ms 18772 KB Output is correct
7 Correct 537 ms 18652 KB Output is correct
8 Correct 695 ms 19836 KB Output is correct
9 Correct 514 ms 19884 KB Output is correct
10 Correct 553 ms 22440 KB Output is correct
11 Correct 665 ms 21548 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2652 KB Output is correct
2 Correct 476 ms 28240 KB Output is correct
3 Correct 506 ms 28028 KB Output is correct
4 Correct 243 ms 28192 KB Output is correct
5 Correct 20 ms 2648 KB Output is correct
6 Correct 195 ms 18772 KB Output is correct
7 Correct 537 ms 18652 KB Output is correct
8 Correct 695 ms 19836 KB Output is correct
9 Correct 514 ms 19884 KB Output is correct
10 Correct 553 ms 22440 KB Output is correct
11 Correct 665 ms 21548 KB Output is correct
12 Correct 22 ms 3396 KB Output is correct
13 Execution timed out 3524 ms 27820 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3468 KB Output is correct
2 Correct 34 ms 3664 KB Output is correct
3 Correct 27 ms 3784 KB Output is correct
4 Correct 56 ms 3872 KB Output is correct
5 Correct 49 ms 3920 KB Output is correct
6 Correct 24 ms 3932 KB Output is correct
7 Correct 18 ms 3416 KB Output is correct
8 Correct 263 ms 19488 KB Output is correct
9 Correct 263 ms 19320 KB Output is correct
10 Correct 24 ms 2652 KB Output is correct
11 Correct 495 ms 28240 KB Output is correct
12 Correct 482 ms 26096 KB Output is correct
13 Correct 248 ms 26276 KB Output is correct
14 Correct 19 ms 2652 KB Output is correct
15 Correct 195 ms 16736 KB Output is correct
16 Correct 531 ms 16812 KB Output is correct
17 Correct 670 ms 17744 KB Output is correct
18 Correct 582 ms 19744 KB Output is correct
19 Correct 519 ms 22452 KB Output is correct
20 Correct 672 ms 21628 KB Output is correct
21 Correct 268 ms 19936 KB Output is correct
22 Correct 283 ms 20284 KB Output is correct
23 Correct 355 ms 20128 KB Output is correct
24 Correct 365 ms 20180 KB Output is correct
25 Correct 508 ms 21852 KB Output is correct
26 Correct 820 ms 19324 KB Output is correct
27 Correct 789 ms 19196 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3468 KB Output is correct
2 Correct 34 ms 3664 KB Output is correct
3 Correct 27 ms 3784 KB Output is correct
4 Correct 56 ms 3872 KB Output is correct
5 Correct 49 ms 3920 KB Output is correct
6 Correct 24 ms 3932 KB Output is correct
7 Correct 18 ms 3416 KB Output is correct
8 Correct 263 ms 19488 KB Output is correct
9 Correct 263 ms 19320 KB Output is correct
10 Correct 24 ms 2652 KB Output is correct
11 Correct 495 ms 28240 KB Output is correct
12 Correct 482 ms 26096 KB Output is correct
13 Correct 248 ms 26276 KB Output is correct
14 Correct 19 ms 2652 KB Output is correct
15 Correct 195 ms 16736 KB Output is correct
16 Correct 531 ms 16812 KB Output is correct
17 Correct 670 ms 17744 KB Output is correct
18 Correct 582 ms 19744 KB Output is correct
19 Correct 519 ms 22452 KB Output is correct
20 Correct 672 ms 21628 KB Output is correct
21 Correct 268 ms 19936 KB Output is correct
22 Correct 283 ms 20284 KB Output is correct
23 Correct 355 ms 20128 KB Output is correct
24 Correct 365 ms 20180 KB Output is correct
25 Correct 508 ms 21852 KB Output is correct
26 Correct 820 ms 19324 KB Output is correct
27 Correct 789 ms 19196 KB Output is correct
28 Correct 22 ms 3420 KB Output is correct
29 Correct 132 ms 3420 KB Output is correct
30 Correct 67 ms 3572 KB Output is correct
31 Correct 374 ms 3408 KB Output is correct
32 Correct 200 ms 4176 KB Output is correct
33 Correct 57 ms 3416 KB Output is correct
34 Correct 21 ms 2900 KB Output is correct
35 Correct 387 ms 19856 KB Output is correct
36 Correct 585 ms 19536 KB Output is correct
37 Correct 759 ms 19796 KB Output is correct
38 Correct 28 ms 3592 KB Output is correct
39 Execution timed out 3531 ms 27920 KB Time limit exceeded
40 Halted 0 ms 0 KB -