oj.uz

Submission #1042493

# Submission time Handle Problem Language Result Execution time Memory
1042493 2024-08-03T05:40:45 Z sleepntsheep Inside information (BOI21_servers) C
100 / 100
 2667 ms 32252 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 600

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 22 ms 7004 KB Output is correct
2 Correct 37 ms 7324 KB Output is correct
3 Correct 39 ms 7620 KB Output is correct
4 Correct 35 ms 7424 KB Output is correct
5 Correct 34 ms 7904 KB Output is correct
6 Correct 44 ms 7504 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 7004 KB Output is correct
2 Correct 37 ms 7324 KB Output is correct
3 Correct 39 ms 7620 KB Output is correct
4 Correct 35 ms 7424 KB Output is correct
5 Correct 34 ms 7904 KB Output is correct
6 Correct 44 ms 7504 KB Output is correct
7 Correct 26 ms 7004 KB Output is correct
8 Correct 110 ms 7252 KB Output is correct
9 Correct 63 ms 7504 KB Output is correct
10 Correct 91 ms 7504 KB Output is correct
11 Correct 38 ms 7768 KB Output is correct
12 Correct 92 ms 7508 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 7044 KB Output is correct
2 Correct 284 ms 19036 KB Output is correct
3 Correct 284 ms 19024 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 7044 KB Output is correct
2 Correct 284 ms 19036 KB Output is correct
3 Correct 284 ms 19024 KB Output is correct
4 Correct 36 ms 7004 KB Output is correct
5 Correct 903 ms 19464 KB Output is correct
6 Correct 1585 ms 19796 KB Output is correct
7 Correct 2607 ms 19536 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 7060 KB Output is correct
2 Correct 245 ms 29492 KB Output is correct
3 Correct 247 ms 29264 KB Output is correct
4 Correct 143 ms 29264 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 7060 KB Output is correct
2 Correct 245 ms 29492 KB Output is correct
3 Correct 247 ms 29264 KB Output is correct
4 Correct 143 ms 29264 KB Output is correct
5 Correct 22 ms 7004 KB Output is correct
6 Correct 453 ms 29776 KB Output is correct
7 Correct 235 ms 29704 KB Output is correct
8 Correct 561 ms 29600 KB Output is correct
9 Correct 623 ms 29520 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 7256 KB Output is correct
2 Correct 163 ms 18080 KB Output is correct
3 Correct 273 ms 18004 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 7256 KB Output is correct
2 Correct 163 ms 18080 KB Output is correct
3 Correct 273 ms 18004 KB Output is correct
4 Correct 24 ms 7004 KB Output is correct
5 Correct 713 ms 18524 KB Output is correct
6 Correct 1310 ms 18464 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 7000 KB Output is correct
2 Correct 247 ms 29408 KB Output is correct
3 Correct 244 ms 29648 KB Output is correct
4 Correct 146 ms 29424 KB Output is correct
5 Correct 23 ms 7004 KB Output is correct
6 Correct 167 ms 18000 KB Output is correct
7 Correct 270 ms 18000 KB Output is correct
8 Correct 241 ms 19092 KB Output is correct
9 Correct 279 ms 19216 KB Output is correct
10 Correct 238 ms 22356 KB Output is correct
11 Correct 255 ms 21328 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 7000 KB Output is correct
2 Correct 247 ms 29408 KB Output is correct
3 Correct 244 ms 29648 KB Output is correct
4 Correct 146 ms 29424 KB Output is correct
5 Correct 23 ms 7004 KB Output is correct
6 Correct 167 ms 18000 KB Output is correct
7 Correct 270 ms 18000 KB Output is correct
8 Correct 241 ms 19092 KB Output is correct
9 Correct 279 ms 19216 KB Output is correct
10 Correct 238 ms 22356 KB Output is correct
11 Correct 255 ms 21328 KB Output is correct
12 Correct 22 ms 7000 KB Output is correct
13 Correct 406 ms 29772 KB Output is correct
14 Correct 265 ms 29860 KB Output is correct
15 Correct 539 ms 29620 KB Output is correct
16 Correct 549 ms 29668 KB Output is correct
17 Correct 24 ms 7004 KB Output is correct
18 Correct 683 ms 18504 KB Output is correct
19 Correct 1323 ms 18368 KB Output is correct
20 Correct 435 ms 19284 KB Output is correct
21 Correct 1137 ms 19588 KB Output is correct
22 Correct 716 ms 21712 KB Output is correct
23 Correct 391 ms 23240 KB Output is correct
24 Correct 292 ms 22792 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 7004 KB Output is correct
2 Correct 37 ms 7512 KB Output is correct
3 Correct 39 ms 7504 KB Output is correct
4 Correct 33 ms 7512 KB Output is correct
5 Correct 27 ms 7876 KB Output is correct
6 Correct 39 ms 7500 KB Output is correct
7 Correct 25 ms 7140 KB Output is correct
8 Correct 283 ms 19024 KB Output is correct
9 Correct 283 ms 19000 KB Output is correct
10 Correct 24 ms 7004 KB Output is correct
11 Correct 245 ms 29264 KB Output is correct
12 Correct 236 ms 29268 KB Output is correct
13 Correct 150 ms 29216 KB Output is correct
14 Correct 23 ms 7128 KB Output is correct
15 Correct 177 ms 18004 KB Output is correct
16 Correct 266 ms 18004 KB Output is correct
17 Correct 242 ms 19024 KB Output is correct
18 Correct 259 ms 19108 KB Output is correct
19 Correct 279 ms 22348 KB Output is correct
20 Correct 264 ms 21492 KB Output is correct
21 Correct 268 ms 19028 KB Output is correct
22 Correct 287 ms 19060 KB Output is correct
23 Correct 292 ms 19332 KB Output is correct
24 Correct 296 ms 19544 KB Output is correct
25 Correct 350 ms 21880 KB Output is correct
26 Correct 258 ms 18260 KB Output is correct
27 Correct 245 ms 18512 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 7004 KB Output is correct
2 Correct 37 ms 7512 KB Output is correct
3 Correct 39 ms 7504 KB Output is correct
4 Correct 33 ms 7512 KB Output is correct
5 Correct 27 ms 7876 KB Output is correct
6 Correct 39 ms 7500 KB Output is correct
7 Correct 25 ms 7140 KB Output is correct
8 Correct 283 ms 19024 KB Output is correct
9 Correct 283 ms 19000 KB Output is correct
10 Correct 24 ms 7004 KB Output is correct
11 Correct 245 ms 29264 KB Output is correct
12 Correct 236 ms 29268 KB Output is correct
13 Correct 150 ms 29216 KB Output is correct
14 Correct 23 ms 7128 KB Output is correct
15 Correct 177 ms 18004 KB Output is correct
16 Correct 266 ms 18004 KB Output is correct
17 Correct 242 ms 19024 KB Output is correct
18 Correct 259 ms 19108 KB Output is correct
19 Correct 279 ms 22348 KB Output is correct
20 Correct 264 ms 21492 KB Output is correct
21 Correct 268 ms 19028 KB Output is correct
22 Correct 287 ms 19060 KB Output is correct
23 Correct 292 ms 19332 KB Output is correct
24 Correct 296 ms 19544 KB Output is correct
25 Correct 350 ms 21880 KB Output is correct
26 Correct 258 ms 18260 KB Output is correct
27 Correct 245 ms 18512 KB Output is correct
28 Correct 23 ms 7000 KB Output is correct
29 Correct 84 ms 7428 KB Output is correct
30 Correct 64 ms 7648 KB Output is correct
31 Correct 56 ms 7504 KB Output is correct
32 Correct 38 ms 7760 KB Output is correct
33 Correct 90 ms 7604 KB Output is correct
34 Correct 29 ms 6992 KB Output is correct
35 Correct 833 ms 19464 KB Output is correct
36 Correct 1550 ms 19896 KB Output is correct
37 Correct 2637 ms 19624 KB Output is correct
38 Correct 23 ms 7004 KB Output is correct
39 Correct 410 ms 29592 KB Output is correct
40 Correct 277 ms 29780 KB Output is correct
41 Correct 542 ms 29720 KB Output is correct
42 Correct 541 ms 32252 KB Output is correct
43 Correct 26 ms 7860 KB Output is correct
44 Correct 657 ms 21332 KB Output is correct
45 Correct 1295 ms 21476 KB Output is correct
46 Correct 424 ms 22096 KB Output is correct
47 Correct 1174 ms 22496 KB Output is correct
48 Correct 719 ms 24412 KB Output is correct
49 Correct 398 ms 26196 KB Output is correct
50 Correct 316 ms 26196 KB Output is correct
51 Correct 1690 ms 22864 KB Output is correct
52 Correct 2390 ms 22448 KB Output is correct
53 Correct 2667 ms 22132 KB Output is correct
54 Correct 1570 ms 22908 KB Output is correct
55 Correct 2533 ms 22448 KB Output is correct
56 Correct 1210 ms 22996 KB Output is correct
57 Correct 916 ms 24880 KB Output is correct
58 Correct 874 ms 21460 KB Output is correct
59 Correct 253 ms 21844 KB Output is correct