oj.uz

Submission #1042494

# Submission time Handle Problem Language Result Execution time Memory
1042494 2024-08-03T05:41:58 Z sleepntsheep Inside information (BOI21_servers) C
100 / 100
 1707 ms 29868 KB 
#include <string.h>
#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 300

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

int ds_find(int i) {
    return ds[i] == i ? i : (ds[i] = ds_find(ds[i]));
}

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) {
    sz[u] = 1;
    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;
        up[v] = fh[u][j];
        dfs(v, u);
        sz[u] += sz[v];
    }

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

    for (int j = 0; j < eo[u]; ++j) {
        int v = eh[u][j];
        if (sz[v] > sz[eh[u][0]]) {
            temp = eh[u][0], eh[u][0] = v, eh[u][j] = temp;
            temp = fh[u][0], fh[u][0] = fh[u][j], fh[u][j] = temp;
        }
    }
}

void efs(int u, int hd) {
    tin[u] = timer++;
    hld[u] = hd;
    if (eo[u])
        efs(eh[u][0], hd);
    for (int j = 1; j < eo[u]; ++j)
        efs(eh[u][j], eh[u][j]);
    tout[u] = timer - 1;
}

int lca(int u, int v) {
    while (hld[u] != hld[v])
        if (dd[hld[u]] >= dd[hld[v]]) u = pp[hld[u]];
        else v = pp[hld[v]];
    return dd[u] <= dd[v] ? u : v;
}

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

void build(int ii, int tme) {
    for (int i = 1; i <= n; ++i)
        dp[i] = 1;
    for (int i = 1; i <= n; ++i)
        ds_find(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);
    for (int i = 1; i <= n; ++i)
        ds[i] = i;

    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] = 1;
    dfs(1, 1);
    efs(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) {
            for (int k = at; k <= i; ++k)
                if (qq[k].type[0] == 'S')
                    ds[ds_find(qq[k].a)] = qq[k].b;
            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 &&
                            ds[a] != ds[focus] && query_yesno(focus, a, j - 1))
                        ++addition, counted[a] = i + 1;
                    if (counted[b] != i + 1 && 
                            ds[b] != ds[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:36:26: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   36 |     else if (0 == (o & o - 1)) eh[i] = (int*)realloc(eh[i], 2 * o * sizeof **eh);
      |                        ~~^~~
servers.c: In function 'main':
servers.c:156:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |     scanf("%d%d", &n, &q);
      |     ^~~~~~~~~~~~~~~~~~~~~
servers.c:165:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |         scanf(" %s%d", s, &a);
      |         ^~~~~~~~~~~~~~~~~~~~~
servers.c:167:13: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |             scanf("%d", &b);
      |             ^~~~~~~~~~~~~~~
servers.c:170:13: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |             scanf("%d", &b);
      |             ^~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 7000 KB Output is correct
2 Correct 51 ms 7504 KB Output is correct
3 Correct 51 ms 7508 KB Output is correct
4 Correct 45 ms 7508 KB Output is correct
5 Correct 48 ms 7708 KB Output is correct
6 Correct 57 ms 7420 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 7000 KB Output is correct
2 Correct 51 ms 7504 KB Output is correct
3 Correct 51 ms 7508 KB Output is correct
4 Correct 45 ms 7508 KB Output is correct
5 Correct 48 ms 7708 KB Output is correct
6 Correct 57 ms 7420 KB Output is correct
7 Correct 33 ms 7056 KB Output is correct
8 Correct 82 ms 7344 KB Output is correct
9 Correct 64 ms 7504 KB Output is correct
10 Correct 55 ms 7548 KB Output is correct
11 Correct 40 ms 7760 KB Output is correct
12 Correct 71 ms 7676 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 7068 KB Output is correct
2 Correct 492 ms 19068 KB Output is correct
3 Correct 477 ms 19116 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 7068 KB Output is correct
2 Correct 492 ms 19068 KB Output is correct
3 Correct 477 ms 19116 KB Output is correct
4 Correct 35 ms 6996 KB Output is correct
5 Correct 797 ms 19516 KB Output is correct
6 Correct 1069 ms 19844 KB Output is correct
7 Correct 1529 ms 19688 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 7036 KB Output is correct
2 Correct 415 ms 29268 KB Output is correct
3 Correct 414 ms 29264 KB Output is correct
4 Correct 225 ms 29520 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 7036 KB Output is correct
2 Correct 415 ms 29268 KB Output is correct
3 Correct 414 ms 29264 KB Output is correct
4 Correct 225 ms 29520 KB Output is correct
5 Correct 30 ms 7000 KB Output is correct
6 Correct 529 ms 29564 KB Output is correct
7 Correct 273 ms 29780 KB Output is correct
8 Correct 633 ms 29528 KB Output is correct
9 Correct 561 ms 29592 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 7004 KB Output is correct
2 Correct 261 ms 18004 KB Output is correct
3 Correct 474 ms 18288 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 7004 KB Output is correct
2 Correct 261 ms 18004 KB Output is correct
3 Correct 474 ms 18288 KB Output is correct
4 Correct 30 ms 7000 KB Output is correct
5 Correct 534 ms 18508 KB Output is correct
6 Correct 979 ms 18516 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 7000 KB Output is correct
2 Correct 418 ms 29344 KB Output is correct
3 Correct 412 ms 29396 KB Output is correct
4 Correct 223 ms 29264 KB Output is correct
5 Correct 30 ms 7004 KB Output is correct
6 Correct 262 ms 18032 KB Output is correct
7 Correct 492 ms 18032 KB Output is correct
8 Correct 406 ms 19024 KB Output is correct
9 Correct 489 ms 19024 KB Output is correct
10 Correct 421 ms 22356 KB Output is correct
11 Correct 409 ms 21584 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 7000 KB Output is correct
2 Correct 418 ms 29344 KB Output is correct
3 Correct 412 ms 29396 KB Output is correct
4 Correct 223 ms 29264 KB Output is correct
5 Correct 30 ms 7004 KB Output is correct
6 Correct 262 ms 18032 KB Output is correct
7 Correct 492 ms 18032 KB Output is correct
8 Correct 406 ms 19024 KB Output is correct
9 Correct 489 ms 19024 KB Output is correct
10 Correct 421 ms 22356 KB Output is correct
11 Correct 409 ms 21584 KB Output is correct
12 Correct 28 ms 6996 KB Output is correct
13 Correct 516 ms 29868 KB Output is correct
14 Correct 275 ms 29776 KB Output is correct
15 Correct 565 ms 29600 KB Output is correct
16 Correct 560 ms 29524 KB Output is correct
17 Correct 30 ms 7000 KB Output is correct
18 Correct 508 ms 18392 KB Output is correct
19 Correct 995 ms 18364 KB Output is correct
20 Correct 503 ms 19368 KB Output is correct
21 Correct 913 ms 19488 KB Output is correct
22 Correct 706 ms 21736 KB Output is correct
23 Correct 577 ms 23268 KB Output is correct
24 Correct 533 ms 22868 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 7000 KB Output is correct
2 Correct 52 ms 7312 KB Output is correct
3 Correct 51 ms 7504 KB Output is correct
4 Correct 46 ms 7532 KB Output is correct
5 Correct 38 ms 8024 KB Output is correct
6 Correct 50 ms 7508 KB Output is correct
7 Correct 37 ms 6996 KB Output is correct
8 Correct 566 ms 19000 KB Output is correct
9 Correct 531 ms 19088 KB Output is correct
10 Correct 31 ms 7004 KB Output is correct
11 Correct 444 ms 29284 KB Output is correct
12 Correct 418 ms 29344 KB Output is correct
13 Correct 239 ms 29268 KB Output is correct
14 Correct 30 ms 7004 KB Output is correct
15 Correct 267 ms 18156 KB Output is correct
16 Correct 551 ms 18072 KB Output is correct
17 Correct 447 ms 19160 KB Output is correct
18 Correct 457 ms 19280 KB Output is correct
19 Correct 444 ms 22352 KB Output is correct
20 Correct 427 ms 21332 KB Output is correct
21 Correct 474 ms 19096 KB Output is correct
22 Correct 485 ms 19028 KB Output is correct
23 Correct 583 ms 19540 KB Output is correct
24 Correct 538 ms 19800 KB Output is correct
25 Correct 650 ms 21840 KB Output is correct
26 Correct 455 ms 18356 KB Output is correct
27 Correct 430 ms 18476 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 7000 KB Output is correct
2 Correct 52 ms 7312 KB Output is correct
3 Correct 51 ms 7504 KB Output is correct
4 Correct 46 ms 7532 KB Output is correct
5 Correct 38 ms 8024 KB Output is correct
6 Correct 50 ms 7508 KB Output is correct
7 Correct 37 ms 6996 KB Output is correct
8 Correct 566 ms 19000 KB Output is correct
9 Correct 531 ms 19088 KB Output is correct
10 Correct 31 ms 7004 KB Output is correct
11 Correct 444 ms 29284 KB Output is correct
12 Correct 418 ms 29344 KB Output is correct
13 Correct 239 ms 29268 KB Output is correct
14 Correct 30 ms 7004 KB Output is correct
15 Correct 267 ms 18156 KB Output is correct
16 Correct 551 ms 18072 KB Output is correct
17 Correct 447 ms 19160 KB Output is correct
18 Correct 457 ms 19280 KB Output is correct
19 Correct 444 ms 22352 KB Output is correct
20 Correct 427 ms 21332 KB Output is correct
21 Correct 474 ms 19096 KB Output is correct
22 Correct 485 ms 19028 KB Output is correct
23 Correct 583 ms 19540 KB Output is correct
24 Correct 538 ms 19800 KB Output is correct
25 Correct 650 ms 21840 KB Output is correct
26 Correct 455 ms 18356 KB Output is correct
27 Correct 430 ms 18476 KB Output is correct
28 Correct 30 ms 7004 KB Output is correct
29 Correct 78 ms 7408 KB Output is correct
30 Correct 64 ms 7520 KB Output is correct
31 Correct 58 ms 7508 KB Output is correct
32 Correct 46 ms 7680 KB Output is correct
33 Correct 71 ms 7696 KB Output is correct
34 Correct 32 ms 7196 KB Output is correct
35 Correct 820 ms 19552 KB Output is correct
36 Correct 1083 ms 19792 KB Output is correct
37 Correct 1569 ms 19536 KB Output is correct
38 Correct 29 ms 7004 KB Output is correct
39 Correct 511 ms 29524 KB Output is correct
40 Correct 290 ms 29788 KB Output is correct
41 Correct 627 ms 29624 KB Output is correct
42 Correct 677 ms 29520 KB Output is correct
43 Correct 30 ms 7132 KB Output is correct
44 Correct 521 ms 18572 KB Output is correct
45 Correct 1094 ms 18276 KB Output is correct
46 Correct 522 ms 19028 KB Output is correct
47 Correct 907 ms 19536 KB Output is correct
48 Correct 702 ms 21592 KB Output is correct
49 Correct 617 ms 23356 KB Output is correct
50 Correct 545 ms 22868 KB Output is correct
51 Correct 1184 ms 19828 KB Output is correct
52 Correct 1545 ms 19808 KB Output is correct
53 Correct 1707 ms 19652 KB Output is correct
54 Correct 1174 ms 19880 KB Output is correct
55 Correct 1627 ms 19900 KB Output is correct
56 Correct 988 ms 20048 KB Output is correct
57 Correct 969 ms 21840 KB Output is correct
58 Correct 818 ms 18768 KB Output is correct
59 Correct 461 ms 18304 KB Output is correct