oj.uz

Submission #1042442

# Submission time Handle Problem Language Result Execution time Memory
1042442 2024-08-03T04:32:45 Z sleepntsheep Inside information (BOI21_servers) C
50 / 100
 3500 ms 25464 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 900

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

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) {
    tin[u] = timer++;
    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);
    }
    tout[u] = timer - 1;

    for (int j = 0; j < eo[u]; ++j) if (eh[u][j] == p) {
        for (int k = j + 1; k < eo[u]; ++k)
            eh[u][k - 1] = eh[u][k];
        --eo[u];
        eh[u][eo[u]] = p;
        break;
    }
}

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

int navigate(int u, int v) {
    int lb = -1, ub = eo[u],z=v;
    while (ub-lb>1){
        int md=lb+(ub-lb)/2;
        if(tin[eh[u][md]]<=tin[v])lb=md,z=eh[u][md];
        else ub=md;
    }
    return z;
}

/* 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], comp[N];

void efs(int u, int time, int root) {
    comp[u] = root;
    int ee = u > 1? eo[u] : eo[u]-1;
    for (int j = 0; j <= ee; ++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 = 1; i <= n; ++i)
        if (comp[i] == -1)
            efs(i, tme, 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);

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

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 6744 KB Output is correct
2 Correct 39 ms 7296 KB Output is correct
3 Correct 36 ms 7372 KB Output is correct
4 Correct 45 ms 7336 KB Output is correct
5 Correct 43 ms 7348 KB Output is correct
6 Correct 38 ms 7164 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 6744 KB Output is correct
2 Correct 39 ms 7296 KB Output is correct
3 Correct 36 ms 7372 KB Output is correct
4 Correct 45 ms 7336 KB Output is correct
5 Correct 43 ms 7348 KB Output is correct
6 Correct 38 ms 7164 KB Output is correct
7 Correct 22 ms 6748 KB Output is correct
8 Incorrect 109 ms 7248 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 24 ms 6852 KB Output is correct
2 Correct 380 ms 18592 KB Output is correct
3 Correct 383 ms 18512 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6852 KB Output is correct
2 Correct 380 ms 18592 KB Output is correct
3 Correct 383 ms 18512 KB Output is correct
4 Correct 31 ms 6748 KB Output is correct
5 Correct 1312 ms 19092 KB Output is correct
6 Correct 2436 ms 19280 KB Output is correct
7 Execution timed out 3528 ms 19024 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6744 KB Output is correct
2 Correct 673 ms 25176 KB Output is correct
3 Correct 643 ms 25168 KB Output is correct
4 Correct 289 ms 25172 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6744 KB Output is correct
2 Correct 673 ms 25176 KB Output is correct
3 Correct 643 ms 25168 KB Output is correct
4 Correct 289 ms 25172 KB Output is correct
5 Correct 21 ms 6748 KB Output is correct
6 Execution timed out 3564 ms 25428 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6928 KB Output is correct
2 Correct 252 ms 17572 KB Output is correct
3 Correct 644 ms 17748 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6928 KB Output is correct
2 Correct 252 ms 17572 KB Output is correct
3 Correct 644 ms 17748 KB Output is correct
4 Correct 23 ms 6744 KB Output is correct
5 Incorrect 523 ms 18000 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 20 ms 6748 KB Output is correct
2 Correct 731 ms 25084 KB Output is correct
3 Correct 763 ms 25024 KB Output is correct
4 Correct 312 ms 25168 KB Output is correct
5 Correct 21 ms 6904 KB Output is correct
6 Correct 257 ms 17596 KB Output is correct
7 Correct 724 ms 17672 KB Output is correct
8 Correct 924 ms 18692 KB Output is correct
9 Correct 748 ms 18768 KB Output is correct
10 Correct 633 ms 20372 KB Output is correct
11 Correct 810 ms 19800 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6748 KB Output is correct
2 Correct 731 ms 25084 KB Output is correct
3 Correct 763 ms 25024 KB Output is correct
4 Correct 312 ms 25168 KB Output is correct
5 Correct 21 ms 6904 KB Output is correct
6 Correct 257 ms 17596 KB Output is correct
7 Correct 724 ms 17672 KB Output is correct
8 Correct 924 ms 18692 KB Output is correct
9 Correct 748 ms 18768 KB Output is correct
10 Correct 633 ms 20372 KB Output is correct
11 Correct 810 ms 19800 KB Output is correct
12 Correct 27 ms 6748 KB Output is correct
13 Execution timed out 3586 ms 25356 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6748 KB Output is correct
2 Correct 38 ms 7192 KB Output is correct
3 Correct 45 ms 7252 KB Output is correct
4 Correct 45 ms 7256 KB Output is correct
5 Correct 42 ms 7512 KB Output is correct
6 Correct 38 ms 7252 KB Output is correct
7 Correct 23 ms 6748 KB Output is correct
8 Correct 357 ms 18524 KB Output is correct
9 Correct 368 ms 18512 KB Output is correct
10 Correct 21 ms 6744 KB Output is correct
11 Correct 666 ms 25168 KB Output is correct
12 Correct 658 ms 25464 KB Output is correct
13 Correct 314 ms 25080 KB Output is correct
14 Correct 20 ms 6744 KB Output is correct
15 Correct 241 ms 17488 KB Output is correct
16 Correct 629 ms 17912 KB Output is correct
17 Correct 785 ms 18772 KB Output is correct
18 Correct 708 ms 18768 KB Output is correct
19 Correct 613 ms 20372 KB Output is correct
20 Correct 762 ms 19868 KB Output is correct
21 Correct 380 ms 18536 KB Output is correct
22 Correct 399 ms 18512 KB Output is correct
23 Correct 432 ms 19240 KB Output is correct
24 Correct 423 ms 19008 KB Output is correct
25 Correct 724 ms 20308 KB Output is correct
26 Correct 1006 ms 17988 KB Output is correct
27 Correct 958 ms 18000 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6748 KB Output is correct
2 Correct 38 ms 7192 KB Output is correct
3 Correct 45 ms 7252 KB Output is correct
4 Correct 45 ms 7256 KB Output is correct
5 Correct 42 ms 7512 KB Output is correct
6 Correct 38 ms 7252 KB Output is correct
7 Correct 23 ms 6748 KB Output is correct
8 Correct 357 ms 18524 KB Output is correct
9 Correct 368 ms 18512 KB Output is correct
10 Correct 21 ms 6744 KB Output is correct
11 Correct 666 ms 25168 KB Output is correct
12 Correct 658 ms 25464 KB Output is correct
13 Correct 314 ms 25080 KB Output is correct
14 Correct 20 ms 6744 KB Output is correct
15 Correct 241 ms 17488 KB Output is correct
16 Correct 629 ms 17912 KB Output is correct
17 Correct 785 ms 18772 KB Output is correct
18 Correct 708 ms 18768 KB Output is correct
19 Correct 613 ms 20372 KB Output is correct
20 Correct 762 ms 19868 KB Output is correct
21 Correct 380 ms 18536 KB Output is correct
22 Correct 399 ms 18512 KB Output is correct
23 Correct 432 ms 19240 KB Output is correct
24 Correct 423 ms 19008 KB Output is correct
25 Correct 724 ms 20308 KB Output is correct
26 Correct 1006 ms 17988 KB Output is correct
27 Correct 958 ms 18000 KB Output is correct
28 Correct 22 ms 6748 KB Output is correct
29 Incorrect 107 ms 7248 KB Extra information in the output file
30 Halted 0 ms 0 KB -