oj.uz

Submission #1042419

# Submission time Handle Problem Language Result Execution time Memory
1042419 2024-08-03T04:15:29 Z sleepntsheep Inside information (BOI21_servers) C
65 / 100
 3500 ms 29268 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 1500

int n, q, pp[N], jj[N], dd[N], up[N], temp, inc[N];

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

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

/* 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;
    ua = anc(u, dd[a] + 1);
    va = anc(v, dd[a] + 1);

    if (u == a) {
        return inc[v] - inc[va] == dd[v] - dd[va] && up[v] <= time;
    }
    if (v == a) {
        return inc[u] - inc[ua] == 0 && up[ua] <= time;
    }

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

    for (int i = 1; i <= n; ++i)
        if (comp[i] == -1)
            efs(i, tme, i);
}

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:130:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |     scanf("%d%d", &n, &q);
      |     ^~~~~~~~~~~~~~~~~~~~~
servers.c:137:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |         scanf(" %s%d", s, &a);
      |         ^~~~~~~~~~~~~~~~~~~~~
servers.c:139:13: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |             scanf("%d", &b);
      |             ^~~~~~~~~~~~~~~
servers.c:142:13: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |             scanf("%d", &b);
      |             ^~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3668 KB Output is correct
2 Correct 34 ms 4036 KB Output is correct
3 Correct 27 ms 4092 KB Output is correct
4 Correct 48 ms 4180 KB Output is correct
5 Correct 46 ms 4188 KB Output is correct
6 Correct 25 ms 4188 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3668 KB Output is correct
2 Correct 34 ms 4036 KB Output is correct
3 Correct 27 ms 4092 KB Output is correct
4 Correct 48 ms 4180 KB Output is correct
5 Correct 46 ms 4188 KB Output is correct
6 Correct 25 ms 4188 KB Output is correct
7 Correct 22 ms 3664 KB Output is correct
8 Correct 144 ms 4168 KB Output is correct
9 Correct 84 ms 3920 KB Output is correct
10 Correct 431 ms 3796 KB Output is correct
11 Correct 244 ms 3924 KB Output is correct
12 Correct 65 ms 3920 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3160 KB Output is correct
2 Correct 227 ms 20104 KB Output is correct
3 Correct 226 ms 20304 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3160 KB Output is correct
2 Correct 227 ms 20104 KB Output is correct
3 Correct 226 ms 20304 KB Output is correct
4 Correct 31 ms 2996 KB Output is correct
5 Correct 371 ms 20820 KB Output is correct
6 Correct 625 ms 20060 KB Output is correct
7 Correct 935 ms 20304 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2900 KB Output is correct
2 Correct 405 ms 29268 KB Output is correct
3 Correct 380 ms 29252 KB Output is correct
4 Correct 206 ms 28756 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2900 KB Output is correct
2 Correct 405 ms 29268 KB Output is correct
3 Correct 380 ms 29252 KB Output is correct
4 Correct 206 ms 28756 KB Output is correct
5 Correct 25 ms 5720 KB Output is correct
6 Execution timed out 3571 ms 28740 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 5716 KB Output is correct
2 Correct 177 ms 19536 KB Output is correct
3 Correct 411 ms 19840 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 5716 KB Output is correct
2 Correct 177 ms 19536 KB Output is correct
3 Correct 411 ms 19840 KB Output is correct
4 Correct 22 ms 5720 KB Output is correct
5 Correct 817 ms 19644 KB Output is correct
6 Correct 1723 ms 19848 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 5724 KB Output is correct
2 Correct 415 ms 29228 KB Output is correct
3 Correct 398 ms 29268 KB Output is correct
4 Correct 207 ms 29128 KB Output is correct
5 Correct 19 ms 5724 KB Output is correct
6 Correct 168 ms 19676 KB Output is correct
7 Correct 459 ms 19732 KB Output is correct
8 Correct 504 ms 20820 KB Output is correct
9 Correct 441 ms 20736 KB Output is correct
10 Correct 412 ms 23268 KB Output is correct
11 Correct 494 ms 22612 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 5724 KB Output is correct
2 Correct 415 ms 29228 KB Output is correct
3 Correct 398 ms 29268 KB Output is correct
4 Correct 207 ms 29128 KB Output is correct
5 Correct 19 ms 5724 KB Output is correct
6 Correct 168 ms 19676 KB Output is correct
7 Correct 459 ms 19732 KB Output is correct
8 Correct 504 ms 20820 KB Output is correct
9 Correct 441 ms 20736 KB Output is correct
10 Correct 412 ms 23268 KB Output is correct
11 Correct 494 ms 22612 KB Output is correct
12 Correct 22 ms 5780 KB Output is correct
13 Execution timed out 3566 ms 28816 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 5656 KB Output is correct
2 Correct 32 ms 6492 KB Output is correct
3 Correct 25 ms 6744 KB Output is correct
4 Correct 61 ms 6616 KB Output is correct
5 Correct 46 ms 6824 KB Output is correct
6 Correct 24 ms 6700 KB Output is correct
7 Correct 18 ms 5772 KB Output is correct
8 Correct 213 ms 20180 KB Output is correct
9 Correct 214 ms 20264 KB Output is correct
10 Correct 20 ms 5724 KB Output is correct
11 Correct 411 ms 29132 KB Output is correct
12 Correct 399 ms 29268 KB Output is correct
13 Correct 215 ms 29012 KB Output is correct
14 Correct 21 ms 5724 KB Output is correct
15 Correct 169 ms 19728 KB Output is correct
16 Correct 402 ms 19620 KB Output is correct
17 Correct 570 ms 20716 KB Output is correct
18 Correct 415 ms 20768 KB Output is correct
19 Correct 416 ms 23124 KB Output is correct
20 Correct 515 ms 22520 KB Output is correct
21 Correct 223 ms 20816 KB Output is correct
22 Correct 236 ms 20736 KB Output is correct
23 Correct 267 ms 20996 KB Output is correct
24 Correct 258 ms 21012 KB Output is correct
25 Correct 396 ms 22868 KB Output is correct
26 Correct 606 ms 20028 KB Output is correct
27 Correct 605 ms 20160 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 5656 KB Output is correct
2 Correct 32 ms 6492 KB Output is correct
3 Correct 25 ms 6744 KB Output is correct
4 Correct 61 ms 6616 KB Output is correct
5 Correct 46 ms 6824 KB Output is correct
6 Correct 24 ms 6700 KB Output is correct
7 Correct 18 ms 5772 KB Output is correct
8 Correct 213 ms 20180 KB Output is correct
9 Correct 214 ms 20264 KB Output is correct
10 Correct 20 ms 5724 KB Output is correct
11 Correct 411 ms 29132 KB Output is correct
12 Correct 399 ms 29268 KB Output is correct
13 Correct 215 ms 29012 KB Output is correct
14 Correct 21 ms 5724 KB Output is correct
15 Correct 169 ms 19728 KB Output is correct
16 Correct 402 ms 19620 KB Output is correct
17 Correct 570 ms 20716 KB Output is correct
18 Correct 415 ms 20768 KB Output is correct
19 Correct 416 ms 23124 KB Output is correct
20 Correct 515 ms 22520 KB Output is correct
21 Correct 223 ms 20816 KB Output is correct
22 Correct 236 ms 20736 KB Output is correct
23 Correct 267 ms 20996 KB Output is correct
24 Correct 258 ms 21012 KB Output is correct
25 Correct 396 ms 22868 KB Output is correct
26 Correct 606 ms 20028 KB Output is correct
27 Correct 605 ms 20160 KB Output is correct
28 Correct 22 ms 5676 KB Output is correct
29 Correct 146 ms 6364 KB Output is correct
30 Correct 81 ms 6480 KB Output is correct
31 Correct 446 ms 6424 KB Output is correct
32 Correct 239 ms 6484 KB Output is correct
33 Correct 67 ms 6484 KB Output is correct
34 Correct 22 ms 5712 KB Output is correct
35 Correct 350 ms 20784 KB Output is correct
36 Correct 612 ms 20116 KB Output is correct
37 Correct 838 ms 20292 KB Output is correct
38 Correct 23 ms 5720 KB Output is correct
39 Execution timed out 3551 ms 27232 KB Time limit exceeded
40 Halted 0 ms 0 KB -