oj.uz

Submission #1042420

# Submission time Handle Problem Language Result Execution time Memory
1042420 2024-08-03T04:17:30 Z sleepntsheep Inside information (BOI21_servers) C
10 / 100
 3500 ms 26132 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 100

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 64 ms 4968 KB Output is correct
2 Correct 124 ms 5200 KB Output is correct
3 Correct 107 ms 5204 KB Output is correct
4 Correct 142 ms 5204 KB Output is correct
5 Correct 171 ms 5516 KB Output is correct
6 Correct 89 ms 5336 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 64 ms 4968 KB Output is correct
2 Correct 124 ms 5200 KB Output is correct
3 Correct 107 ms 5204 KB Output is correct
4 Correct 142 ms 5204 KB Output is correct
5 Correct 171 ms 5516 KB Output is correct
6 Correct 89 ms 5336 KB Output is correct
7 Correct 57 ms 4696 KB Output is correct
8 Correct 130 ms 5204 KB Output is correct
9 Correct 138 ms 5400 KB Output is correct
10 Correct 159 ms 5204 KB Output is correct
11 Correct 169 ms 5460 KB Output is correct
12 Correct 89 ms 5456 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 54 ms 4696 KB Output is correct
2 Correct 2584 ms 17844 KB Output is correct
3 Correct 2695 ms 17748 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 54 ms 4696 KB Output is correct
2 Correct 2584 ms 17844 KB Output is correct
3 Correct 2695 ms 17748 KB Output is correct
4 Correct 64 ms 4760 KB Output is correct
5 Correct 2590 ms 18156 KB Output is correct
6 Correct 2646 ms 18436 KB Output is correct
7 Correct 2674 ms 18256 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 4784 KB Output is correct
2 Execution timed out 3577 ms 26132 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 4784 KB Output is correct
2 Execution timed out 3577 ms 26132 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 4696 KB Output is correct
2 Correct 1875 ms 16720 KB Output is correct
3 Execution timed out 3562 ms 16700 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 4696 KB Output is correct
2 Correct 1875 ms 16720 KB Output is correct
3 Execution timed out 3562 ms 16700 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 58 ms 4828 KB Output is correct
2 Execution timed out 3567 ms 26024 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 58 ms 4828 KB Output is correct
2 Execution timed out 3567 ms 26024 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 4700 KB Output is correct
2 Correct 136 ms 5068 KB Output is correct
3 Correct 103 ms 5204 KB Output is correct
4 Correct 141 ms 5200 KB Output is correct
5 Correct 163 ms 5376 KB Output is correct
6 Correct 91 ms 5200 KB Output is correct
7 Correct 61 ms 4800 KB Output is correct
8 Correct 2662 ms 17588 KB Output is correct
9 Correct 2719 ms 17692 KB Output is correct
10 Correct 62 ms 4692 KB Output is correct
11 Execution timed out 3573 ms 26032 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 4700 KB Output is correct
2 Correct 136 ms 5068 KB Output is correct
3 Correct 103 ms 5204 KB Output is correct
4 Correct 141 ms 5200 KB Output is correct
5 Correct 163 ms 5376 KB Output is correct
6 Correct 91 ms 5200 KB Output is correct
7 Correct 61 ms 4800 KB Output is correct
8 Correct 2662 ms 17588 KB Output is correct
9 Correct 2719 ms 17692 KB Output is correct
10 Correct 62 ms 4692 KB Output is correct
11 Execution timed out 3573 ms 26032 KB Time limit exceeded
12 Halted 0 ms 0 KB -