oj.uz

Submission #1042434

# Submission time Handle Problem Language Result Execution time Memory
1042434 2024-08-03T04:30:21 Z sleepntsheep Inside information (BOI21_servers) C
50 / 100
 3500 ms 25452 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=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;
    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 37 ms 7252 KB Output is correct
3 Correct 35 ms 7252 KB Output is correct
4 Correct 45 ms 7252 KB Output is correct
5 Correct 43 ms 7504 KB Output is correct
6 Correct 37 ms 7168 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 37 ms 7252 KB Output is correct
3 Correct 35 ms 7252 KB Output is correct
4 Correct 45 ms 7252 KB Output is correct
5 Correct 43 ms 7504 KB Output is correct
6 Correct 37 ms 7168 KB Output is correct
7 Correct 22 ms 6748 KB Output is correct
8 Incorrect 109 ms 7032 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 24 ms 6744 KB Output is correct
2 Correct 304 ms 18592 KB Output is correct
3 Correct 297 ms 18516 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6744 KB Output is correct
2 Correct 304 ms 18592 KB Output is correct
3 Correct 297 ms 18516 KB Output is correct
4 Correct 28 ms 6880 KB Output is correct
5 Correct 1150 ms 19084 KB Output is correct
6 Correct 2327 ms 19284 KB Output is correct
7 Execution timed out 3542 ms 19020 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 6744 KB Output is correct
2 Correct 573 ms 25076 KB Output is correct
3 Correct 574 ms 25172 KB Output is correct
4 Correct 276 ms 25140 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 6744 KB Output is correct
2 Correct 573 ms 25076 KB Output is correct
3 Correct 574 ms 25172 KB Output is correct
4 Correct 276 ms 25140 KB Output is correct
5 Correct 21 ms 6748 KB Output is correct
6 Execution timed out 3522 ms 25452 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 6744 KB Output is correct
2 Correct 250 ms 17628 KB Output is correct
3 Correct 545 ms 17908 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6744 KB Output is correct
2 Correct 250 ms 17628 KB Output is correct
3 Correct 545 ms 17908 KB Output is correct
4 Correct 21 ms 6932 KB Output is correct
5 Incorrect 527 ms 18092 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 6744 KB Output is correct
2 Correct 585 ms 25072 KB Output is correct
3 Correct 580 ms 25020 KB Output is correct
4 Correct 270 ms 25168 KB Output is correct
5 Correct 20 ms 6940 KB Output is correct
6 Correct 230 ms 17488 KB Output is correct
7 Correct 534 ms 17744 KB Output is correct
8 Correct 623 ms 18516 KB Output is correct
9 Correct 543 ms 18768 KB Output is correct
10 Correct 577 ms 20564 KB Output is correct
11 Correct 732 ms 19812 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6744 KB Output is correct
2 Correct 585 ms 25072 KB Output is correct
3 Correct 580 ms 25020 KB Output is correct
4 Correct 270 ms 25168 KB Output is correct
5 Correct 20 ms 6940 KB Output is correct
6 Correct 230 ms 17488 KB Output is correct
7 Correct 534 ms 17744 KB Output is correct
8 Correct 623 ms 18516 KB Output is correct
9 Correct 543 ms 18768 KB Output is correct
10 Correct 577 ms 20564 KB Output is correct
11 Correct 732 ms 19812 KB Output is correct
12 Correct 23 ms 6744 KB Output is correct
13 Execution timed out 3566 ms 25328 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6748 KB Output is correct
2 Correct 38 ms 7252 KB Output is correct
3 Correct 37 ms 7256 KB Output is correct
4 Correct 42 ms 7228 KB Output is correct
5 Correct 43 ms 7512 KB Output is correct
6 Correct 38 ms 7248 KB Output is correct
7 Correct 25 ms 7000 KB Output is correct
8 Correct 300 ms 18588 KB Output is correct
9 Correct 325 ms 18512 KB Output is correct
10 Correct 21 ms 6744 KB Output is correct
11 Correct 581 ms 25232 KB Output is correct
12 Correct 578 ms 25168 KB Output is correct
13 Correct 290 ms 25168 KB Output is correct
14 Correct 20 ms 6744 KB Output is correct
15 Correct 230 ms 17652 KB Output is correct
16 Correct 543 ms 17720 KB Output is correct
17 Correct 633 ms 18512 KB Output is correct
18 Correct 561 ms 18512 KB Output is correct
19 Correct 600 ms 20392 KB Output is correct
20 Correct 709 ms 19968 KB Output is correct
21 Correct 286 ms 18508 KB Output is correct
22 Correct 283 ms 18768 KB Output is correct
23 Correct 309 ms 19024 KB Output is correct
24 Correct 352 ms 19000 KB Output is correct
25 Correct 692 ms 20304 KB Output is correct
26 Correct 922 ms 18176 KB Output is correct
27 Correct 875 ms 18176 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6748 KB Output is correct
2 Correct 38 ms 7252 KB Output is correct
3 Correct 37 ms 7256 KB Output is correct
4 Correct 42 ms 7228 KB Output is correct
5 Correct 43 ms 7512 KB Output is correct
6 Correct 38 ms 7248 KB Output is correct
7 Correct 25 ms 7000 KB Output is correct
8 Correct 300 ms 18588 KB Output is correct
9 Correct 325 ms 18512 KB Output is correct
10 Correct 21 ms 6744 KB Output is correct
11 Correct 581 ms 25232 KB Output is correct
12 Correct 578 ms 25168 KB Output is correct
13 Correct 290 ms 25168 KB Output is correct
14 Correct 20 ms 6744 KB Output is correct
15 Correct 230 ms 17652 KB Output is correct
16 Correct 543 ms 17720 KB Output is correct
17 Correct 633 ms 18512 KB Output is correct
18 Correct 561 ms 18512 KB Output is correct
19 Correct 600 ms 20392 KB Output is correct
20 Correct 709 ms 19968 KB Output is correct
21 Correct 286 ms 18508 KB Output is correct
22 Correct 283 ms 18768 KB Output is correct
23 Correct 309 ms 19024 KB Output is correct
24 Correct 352 ms 19000 KB Output is correct
25 Correct 692 ms 20304 KB Output is correct
26 Correct 922 ms 18176 KB Output is correct
27 Correct 875 ms 18176 KB Output is correct
28 Correct 22 ms 6744 KB Output is correct
29 Incorrect 109 ms 7212 KB Extra information in the output file
30 Halted 0 ms 0 KB -