oj.uz

Submission #1042389

# Submission time Handle Problem Language Result Execution time Memory
1042389 2024-08-03T03:29:04 Z sleepntsheep Inside information (BOI21_servers) C
32.5 / 100
 3500 ms 30588 KB 
#include <stdio.h>
#include <stdlib.h>

/*
 * 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)
 */

#define N 120001
#define B 300


int n, q, pp[N], jj[N], dd[N], up[N], temp, inc[N], map_time[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;
    int a, b;
    int ans;
} 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 = anc(v, dd[a] + 1);
    int ua = anc(u, 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 p, int time, int root) {
    comp[u] = root;
    for (int j = 0; j < eo[u]; ++j)
        if (eh[u][j] != p && fh[u][j] <= time && comp[eh[u][j]] == -1)
            efs(eh[u][j], u, 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 != '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, 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) {
        char c;
        int a, b;
        scanf(" %c%d", &c, &a);
        if (c == 'S') {
            scanf("%d", &b);
            link(a, b, j++);
            map_time[j - 1] = i;
        } else if (c == 'Q')
            scanf("%d", &b);

        qq[i] = (struct Query){c, a, 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 == 'S') {
            ++j;
        }
        else if (qq[i].type == 'Q') {
            puts(query_yesno(qq[i].b, qq[i].a, j - 1) ? "yes": "no");
        } else {
            int focus = qq[i].a;
            int addition = 0;
            for (int k = at; k < i; ++k)
                if (qq[k].type == '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);
        }

        if (i % B == 0) {
            build(i, j);
            at = i + 1;
        }
    }
}

Compilation message

servers.c: In function 'pus_':
servers.c:30:26: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   30 |     else if (0 == (o & o - 1)) eh[i] = (int*)realloc(eh[i], 2 * o * sizeof **eh);
      |                        ~~^~~
servers.c: In function 'main':
servers.c:127:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |     scanf("%d%d", &n, &q);
      |     ^~~~~~~~~~~~~~~~~~~~~
servers.c:133:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |         scanf(" %c%d", &c, &a);
      |         ^~~~~~~~~~~~~~~~~~~~~~
servers.c:135:13: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |             scanf("%d", &b);
      |             ^~~~~~~~~~~~~~~
servers.c:139:13: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |             scanf("%d", &b);
      |             ^~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 3420 KB Output is correct
2 Correct 67 ms 4512 KB Output is correct
3 Correct 54 ms 4624 KB Output is correct
4 Correct 90 ms 4688 KB Output is correct
5 Correct 90 ms 4852 KB Output is correct
6 Correct 48 ms 4692 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 3420 KB Output is correct
2 Correct 67 ms 4512 KB Output is correct
3 Correct 54 ms 4624 KB Output is correct
4 Correct 90 ms 4688 KB Output is correct
5 Correct 90 ms 4852 KB Output is correct
6 Correct 48 ms 4692 KB Output is correct
7 Correct 39 ms 3416 KB Output is correct
8 Incorrect 90 ms 4176 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 48 ms 3412 KB Output is correct
2 Correct 957 ms 21688 KB Output is correct
3 Correct 1010 ms 21588 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 3412 KB Output is correct
2 Correct 957 ms 21688 KB Output is correct
3 Correct 1010 ms 21588 KB Output is correct
4 Correct 46 ms 3416 KB Output is correct
5 Incorrect 986 ms 21856 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3416 KB Output is correct
2 Correct 1800 ms 30240 KB Output is correct
3 Correct 1824 ms 30292 KB Output is correct
4 Correct 746 ms 30288 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3416 KB Output is correct
2 Correct 1800 ms 30240 KB Output is correct
3 Correct 1824 ms 30292 KB Output is correct
4 Correct 746 ms 30288 KB Output is correct
5 Correct 37 ms 3408 KB Output is correct
6 Execution timed out 3547 ms 30304 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 3420 KB Output is correct
2 Correct 663 ms 20780 KB Output is correct
3 Correct 1983 ms 20852 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 3420 KB Output is correct
2 Correct 663 ms 20780 KB Output is correct
3 Correct 1983 ms 20852 KB Output is correct
4 Correct 43 ms 3784 KB Output is correct
5 Incorrect 795 ms 20880 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 37 ms 3420 KB Output is correct
2 Correct 1774 ms 30200 KB Output is correct
3 Correct 1710 ms 30416 KB Output is correct
4 Correct 749 ms 30380 KB Output is correct
5 Correct 37 ms 3416 KB Output is correct
6 Correct 653 ms 20820 KB Output is correct
7 Correct 1878 ms 20844 KB Output is correct
8 Correct 2262 ms 21932 KB Output is correct
9 Correct 1953 ms 21852 KB Output is correct
10 Correct 1916 ms 24748 KB Output is correct
11 Correct 2329 ms 23892 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3420 KB Output is correct
2 Correct 1774 ms 30200 KB Output is correct
3 Correct 1710 ms 30416 KB Output is correct
4 Correct 749 ms 30380 KB Output is correct
5 Correct 37 ms 3416 KB Output is correct
6 Correct 653 ms 20820 KB Output is correct
7 Correct 1878 ms 20844 KB Output is correct
8 Correct 2262 ms 21932 KB Output is correct
9 Correct 1953 ms 21852 KB Output is correct
10 Correct 1916 ms 24748 KB Output is correct
11 Correct 2329 ms 23892 KB Output is correct
12 Correct 37 ms 3576 KB Output is correct
13 Incorrect 3441 ms 30252 KB Extra information in the output file
14 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 3416 KB Output is correct
2 Correct 73 ms 4432 KB Output is correct
3 Correct 53 ms 4696 KB Output is correct
4 Correct 84 ms 4580 KB Output is correct
5 Correct 89 ms 4688 KB Output is correct
6 Correct 70 ms 4688 KB Output is correct
7 Correct 35 ms 3416 KB Output is correct
8 Correct 947 ms 21568 KB Output is correct
9 Correct 966 ms 21584 KB Output is correct
10 Correct 37 ms 3496 KB Output is correct
11 Correct 1739 ms 30292 KB Output is correct
12 Correct 1791 ms 30408 KB Output is correct
13 Correct 766 ms 30588 KB Output is correct
14 Correct 38 ms 3416 KB Output is correct
15 Correct 700 ms 20756 KB Output is correct
16 Correct 2463 ms 20860 KB Output is correct
17 Correct 3185 ms 21904 KB Output is correct
18 Correct 2069 ms 22036 KB Output is correct
19 Correct 2136 ms 24660 KB Output is correct
20 Correct 3086 ms 23756 KB Output is correct
21 Correct 1031 ms 22212 KB Output is correct
22 Correct 1213 ms 22100 KB Output is correct
23 Correct 1501 ms 22296 KB Output is correct
24 Correct 1443 ms 22460 KB Output is correct
25 Correct 2238 ms 24104 KB Output is correct
26 Correct 3351 ms 21372 KB Output is correct
27 Execution timed out 3574 ms 21436 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 3416 KB Output is correct
2 Correct 73 ms 4432 KB Output is correct
3 Correct 53 ms 4696 KB Output is correct
4 Correct 84 ms 4580 KB Output is correct
5 Correct 89 ms 4688 KB Output is correct
6 Correct 70 ms 4688 KB Output is correct
7 Correct 35 ms 3416 KB Output is correct
8 Correct 947 ms 21568 KB Output is correct
9 Correct 966 ms 21584 KB Output is correct
10 Correct 37 ms 3496 KB Output is correct
11 Correct 1739 ms 30292 KB Output is correct
12 Correct 1791 ms 30408 KB Output is correct
13 Correct 766 ms 30588 KB Output is correct
14 Correct 38 ms 3416 KB Output is correct
15 Correct 700 ms 20756 KB Output is correct
16 Correct 2463 ms 20860 KB Output is correct
17 Correct 3185 ms 21904 KB Output is correct
18 Correct 2069 ms 22036 KB Output is correct
19 Correct 2136 ms 24660 KB Output is correct
20 Correct 3086 ms 23756 KB Output is correct
21 Correct 1031 ms 22212 KB Output is correct
22 Correct 1213 ms 22100 KB Output is correct
23 Correct 1501 ms 22296 KB Output is correct
24 Correct 1443 ms 22460 KB Output is correct
25 Correct 2238 ms 24104 KB Output is correct
26 Correct 3351 ms 21372 KB Output is correct
27 Execution timed out 3574 ms 21436 KB Time limit exceeded
28 Halted 0 ms 0 KB -