oj.uz

Submission #1042431

# Submission time Handle Problem Language Result Execution time Memory
1042431 2024-08-03T04:29:26 Z sleepntsheep Inside information (BOI21_servers) C
50 / 100
 3500 ms 25436 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) {
        for (int k = j + 1; k < eo[u]; ++k)
            eh[u][k - 1] = eh[u][k];
        --eo[u];
        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=u;
    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;
    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 = 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:150:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |     scanf("%d%d", &n, &q);
      |     ^~~~~~~~~~~~~~~~~~~~~
servers.c:157:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |         scanf(" %s%d", s, &a);
      |         ^~~~~~~~~~~~~~~~~~~~~
servers.c:159:13: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |             scanf("%d", &b);
      |             ^~~~~~~~~~~~~~~
servers.c:162:13: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |             scanf("%d", &b);
      |             ^~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6748 KB Output is correct
2 Correct 36 ms 7160 KB Output is correct
3 Correct 34 ms 7260 KB Output is correct
4 Correct 43 ms 7284 KB Output is correct
5 Correct 41 ms 7504 KB Output is correct
6 Correct 41 ms 7252 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6748 KB Output is correct
2 Correct 36 ms 7160 KB Output is correct
3 Correct 34 ms 7260 KB Output is correct
4 Correct 43 ms 7284 KB Output is correct
5 Correct 41 ms 7504 KB Output is correct
6 Correct 41 ms 7252 KB Output is correct
7 Correct 24 ms 6748 KB Output is correct
8 Incorrect 109 ms 7116 KB Extra information in the output file
9 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 7000 KB Output is correct
2 Correct 292 ms 18560 KB Output is correct
3 Correct 305 ms 18516 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 7000 KB Output is correct
2 Correct 292 ms 18560 KB Output is correct
3 Correct 305 ms 18516 KB Output is correct
4 Correct 33 ms 6744 KB Output is correct
5 Correct 1207 ms 19028 KB Output is correct
6 Correct 2395 ms 19348 KB Output is correct
7 Execution timed out 3556 ms 19024 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6744 KB Output is correct
2 Correct 594 ms 25112 KB Output is correct
3 Correct 591 ms 25064 KB Output is correct
4 Correct 297 ms 25172 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6744 KB Output is correct
2 Correct 594 ms 25112 KB Output is correct
3 Correct 591 ms 25064 KB Output is correct
4 Correct 297 ms 25172 KB Output is correct
5 Correct 31 ms 6748 KB Output is correct
6 Execution timed out 3552 ms 25428 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6748 KB Output is correct
2 Correct 238 ms 17488 KB Output is correct
3 Correct 543 ms 17744 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6748 KB Output is correct
2 Correct 238 ms 17488 KB Output is correct
3 Correct 543 ms 17744 KB Output is correct
4 Correct 23 ms 6744 KB Output is correct
5 Incorrect 516 ms 18000 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6748 KB Output is correct
2 Correct 577 ms 25108 KB Output is correct
3 Correct 605 ms 25124 KB Output is correct
4 Correct 288 ms 25168 KB Output is correct
5 Correct 21 ms 6748 KB Output is correct
6 Correct 247 ms 17468 KB Output is correct
7 Correct 556 ms 17736 KB Output is correct
8 Correct 644 ms 18512 KB Output is correct
9 Correct 567 ms 18516 KB Output is correct
10 Correct 637 ms 20304 KB Output is correct
11 Correct 708 ms 19796 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6748 KB Output is correct
2 Correct 577 ms 25108 KB Output is correct
3 Correct 605 ms 25124 KB Output is correct
4 Correct 288 ms 25168 KB Output is correct
5 Correct 21 ms 6748 KB Output is correct
6 Correct 247 ms 17468 KB Output is correct
7 Correct 556 ms 17736 KB Output is correct
8 Correct 644 ms 18512 KB Output is correct
9 Correct 567 ms 18516 KB Output is correct
10 Correct 637 ms 20304 KB Output is correct
11 Correct 708 ms 19796 KB Output is correct
12 Correct 23 ms 6744 KB Output is correct
13 Execution timed out 3508 ms 25436 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6912 KB Output is correct
2 Correct 36 ms 7252 KB Output is correct
3 Correct 34 ms 7260 KB Output is correct
4 Correct 42 ms 7196 KB Output is correct
5 Correct 43 ms 7516 KB Output is correct
6 Correct 39 ms 7256 KB Output is correct
7 Correct 26 ms 7004 KB Output is correct
8 Correct 297 ms 18580 KB Output is correct
9 Correct 298 ms 18556 KB Output is correct
10 Correct 24 ms 6748 KB Output is correct
11 Correct 614 ms 25172 KB Output is correct
12 Correct 566 ms 25188 KB Output is correct
13 Correct 260 ms 25172 KB Output is correct
14 Correct 21 ms 6748 KB Output is correct
15 Correct 236 ms 17492 KB Output is correct
16 Correct 533 ms 17624 KB Output is correct
17 Correct 699 ms 18516 KB Output is correct
18 Correct 538 ms 18768 KB Output is correct
19 Correct 574 ms 20304 KB Output is correct
20 Correct 687 ms 19796 KB Output is correct
21 Correct 288 ms 18516 KB Output is correct
22 Correct 277 ms 18516 KB Output is correct
23 Correct 305 ms 19024 KB Output is correct
24 Correct 296 ms 19024 KB Output is correct
25 Correct 685 ms 20308 KB Output is correct
26 Correct 899 ms 18004 KB Output is correct
27 Correct 876 ms 18044 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6912 KB Output is correct
2 Correct 36 ms 7252 KB Output is correct
3 Correct 34 ms 7260 KB Output is correct
4 Correct 42 ms 7196 KB Output is correct
5 Correct 43 ms 7516 KB Output is correct
6 Correct 39 ms 7256 KB Output is correct
7 Correct 26 ms 7004 KB Output is correct
8 Correct 297 ms 18580 KB Output is correct
9 Correct 298 ms 18556 KB Output is correct
10 Correct 24 ms 6748 KB Output is correct
11 Correct 614 ms 25172 KB Output is correct
12 Correct 566 ms 25188 KB Output is correct
13 Correct 260 ms 25172 KB Output is correct
14 Correct 21 ms 6748 KB Output is correct
15 Correct 236 ms 17492 KB Output is correct
16 Correct 533 ms 17624 KB Output is correct
17 Correct 699 ms 18516 KB Output is correct
18 Correct 538 ms 18768 KB Output is correct
19 Correct 574 ms 20304 KB Output is correct
20 Correct 687 ms 19796 KB Output is correct
21 Correct 288 ms 18516 KB Output is correct
22 Correct 277 ms 18516 KB Output is correct
23 Correct 305 ms 19024 KB Output is correct
24 Correct 296 ms 19024 KB Output is correct
25 Correct 685 ms 20308 KB Output is correct
26 Correct 899 ms 18004 KB Output is correct
27 Correct 876 ms 18044 KB Output is correct
28 Correct 27 ms 6748 KB Output is correct
29 Incorrect 109 ms 7004 KB Extra information in the output file
30 Halted 0 ms 0 KB -