oj.uz

Submission #1042448

# Submission time Handle Problem Language Result Execution time Memory
1042448 2024-08-03T04:35:38 Z sleepntsheep Inside information (BOI21_servers) C
65 / 100
 3500 ms 28688 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], 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];
    while (ub-lb>1){
        int md=lb+(ub-lb)/2;
        if(tin[eh[u][md]]<=tin[v])lb=md;
        else ub=md;
    }
    return eh[u][lb];
}

/* 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

# Verdict Execution time Memory Grader output
1 Correct 22 ms 6744 KB Output is correct
2 Correct 42 ms 7088 KB Output is correct
3 Correct 40 ms 7208 KB Output is correct
4 Correct 56 ms 7364 KB Output is correct
5 Correct 54 ms 7504 KB Output is correct
6 Correct 47 ms 7256 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 6744 KB Output is correct
2 Correct 42 ms 7088 KB Output is correct
3 Correct 40 ms 7208 KB Output is correct
4 Correct 56 ms 7364 KB Output is correct
5 Correct 54 ms 7504 KB Output is correct
6 Correct 47 ms 7256 KB Output is correct
7 Correct 23 ms 6840 KB Output is correct
8 Correct 104 ms 7096 KB Output is correct
9 Correct 75 ms 7252 KB Output is correct
10 Correct 164 ms 7072 KB Output is correct
11 Correct 100 ms 7444 KB Output is correct
12 Correct 98 ms 7244 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 6756 KB Output is correct
2 Correct 471 ms 18584 KB Output is correct
3 Correct 447 ms 18556 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 6756 KB Output is correct
2 Correct 471 ms 18584 KB Output is correct
3 Correct 447 ms 18556 KB Output is correct
4 Correct 26 ms 6748 KB Output is correct
5 Correct 1061 ms 18936 KB Output is correct
6 Correct 1916 ms 19376 KB Output is correct
7 Correct 2971 ms 19168 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6744 KB Output is correct
2 Correct 764 ms 25048 KB Output is correct
3 Correct 733 ms 25172 KB Output is correct
4 Correct 372 ms 25044 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6744 KB Output is correct
2 Correct 764 ms 25048 KB Output is correct
3 Correct 733 ms 25172 KB Output is correct
4 Correct 372 ms 25044 KB Output is correct
5 Correct 23 ms 6748 KB Output is correct
6 Correct 3165 ms 25352 KB Output is correct
7 Correct 1507 ms 28672 KB Output is correct
8 Execution timed out 3569 ms 27808 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 6748 KB Output is correct
2 Correct 360 ms 17696 KB Output is correct
3 Correct 811 ms 17744 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 6748 KB Output is correct
2 Correct 360 ms 17696 KB Output is correct
3 Correct 811 ms 17744 KB Output is correct
4 Correct 27 ms 6748 KB Output is correct
5 Correct 562 ms 18092 KB Output is correct
6 Correct 1200 ms 17988 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 6748 KB Output is correct
2 Correct 694 ms 25228 KB Output is correct
3 Correct 707 ms 25168 KB Output is correct
4 Correct 380 ms 25172 KB Output is correct
5 Correct 21 ms 6748 KB Output is correct
6 Correct 327 ms 17624 KB Output is correct
7 Correct 738 ms 17724 KB Output is correct
8 Correct 983 ms 18512 KB Output is correct
9 Correct 810 ms 18608 KB Output is correct
10 Correct 776 ms 20308 KB Output is correct
11 Correct 913 ms 20048 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 6748 KB Output is correct
2 Correct 694 ms 25228 KB Output is correct
3 Correct 707 ms 25168 KB Output is correct
4 Correct 380 ms 25172 KB Output is correct
5 Correct 21 ms 6748 KB Output is correct
6 Correct 327 ms 17624 KB Output is correct
7 Correct 738 ms 17724 KB Output is correct
8 Correct 983 ms 18512 KB Output is correct
9 Correct 810 ms 18608 KB Output is correct
10 Correct 776 ms 20308 KB Output is correct
11 Correct 913 ms 20048 KB Output is correct
12 Correct 22 ms 6748 KB Output is correct
13 Correct 3316 ms 25464 KB Output is correct
14 Correct 1558 ms 28688 KB Output is correct
15 Execution timed out 3542 ms 28008 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 6744 KB Output is correct
2 Correct 45 ms 7412 KB Output is correct
3 Correct 39 ms 7352 KB Output is correct
4 Correct 47 ms 7248 KB Output is correct
5 Correct 46 ms 7468 KB Output is correct
6 Correct 40 ms 7248 KB Output is correct
7 Correct 24 ms 6744 KB Output is correct
8 Correct 441 ms 18552 KB Output is correct
9 Correct 431 ms 18768 KB Output is correct
10 Correct 21 ms 6748 KB Output is correct
11 Correct 708 ms 25500 KB Output is correct
12 Correct 716 ms 25172 KB Output is correct
13 Correct 388 ms 25092 KB Output is correct
14 Correct 21 ms 6748 KB Output is correct
15 Correct 360 ms 17520 KB Output is correct
16 Correct 792 ms 17728 KB Output is correct
17 Correct 1047 ms 18692 KB Output is correct
18 Correct 780 ms 18608 KB Output is correct
19 Correct 768 ms 20304 KB Output is correct
20 Correct 886 ms 19796 KB Output is correct
21 Correct 449 ms 18512 KB Output is correct
22 Correct 461 ms 18516 KB Output is correct
23 Correct 560 ms 19024 KB Output is correct
24 Correct 503 ms 19024 KB Output is correct
25 Correct 769 ms 20252 KB Output is correct
26 Correct 1220 ms 17828 KB Output is correct
27 Correct 1193 ms 18044 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 6744 KB Output is correct
2 Correct 45 ms 7412 KB Output is correct
3 Correct 39 ms 7352 KB Output is correct
4 Correct 47 ms 7248 KB Output is correct
5 Correct 46 ms 7468 KB Output is correct
6 Correct 40 ms 7248 KB Output is correct
7 Correct 24 ms 6744 KB Output is correct
8 Correct 441 ms 18552 KB Output is correct
9 Correct 431 ms 18768 KB Output is correct
10 Correct 21 ms 6748 KB Output is correct
11 Correct 708 ms 25500 KB Output is correct
12 Correct 716 ms 25172 KB Output is correct
13 Correct 388 ms 25092 KB Output is correct
14 Correct 21 ms 6748 KB Output is correct
15 Correct 360 ms 17520 KB Output is correct
16 Correct 792 ms 17728 KB Output is correct
17 Correct 1047 ms 18692 KB Output is correct
18 Correct 780 ms 18608 KB Output is correct
19 Correct 768 ms 20304 KB Output is correct
20 Correct 886 ms 19796 KB Output is correct
21 Correct 449 ms 18512 KB Output is correct
22 Correct 461 ms 18516 KB Output is correct
23 Correct 560 ms 19024 KB Output is correct
24 Correct 503 ms 19024 KB Output is correct
25 Correct 769 ms 20252 KB Output is correct
26 Correct 1220 ms 17828 KB Output is correct
27 Correct 1193 ms 18044 KB Output is correct
28 Correct 23 ms 6748 KB Output is correct
29 Correct 117 ms 7012 KB Output is correct
30 Correct 75 ms 7248 KB Output is correct
31 Correct 166 ms 7280 KB Output is correct
32 Correct 98 ms 7448 KB Output is correct
33 Correct 99 ms 7336 KB Output is correct
34 Correct 26 ms 6748 KB Output is correct
35 Correct 1082 ms 19000 KB Output is correct
36 Correct 1881 ms 19344 KB Output is correct
37 Correct 2931 ms 19128 KB Output is correct
38 Correct 27 ms 6848 KB Output is correct
39 Correct 3072 ms 25944 KB Output is correct
40 Correct 1524 ms 28688 KB Output is correct
41 Execution timed out 3556 ms 27988 KB Time limit exceeded
42 Halted 0 ms 0 KB -