oj.uz

답안 #1042427

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1042427 2024-08-03T04:26:13 Z sleepntsheep Inside information (BOI21_servers) C
50 / 100
 3500 ms 25352 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];
        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];
    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 = navigate(a, v), ua = navigate(a, u);

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

Subtask #1
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 6748 KB Output is correct
2 Correct 39 ms 7252 KB Output is correct
3 Correct 34 ms 7324 KB Output is correct
4 Correct 45 ms 7504 KB Output is correct
5 Correct 42 ms 7508 KB Output is correct
6 Correct 37 ms 7252 KB Output is correct

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 6748 KB Output is correct
2 Correct 39 ms 7252 KB Output is correct
3 Correct 34 ms 7324 KB Output is correct
4 Correct 45 ms 7504 KB Output is correct
5 Correct 42 ms 7508 KB Output is correct
6 Correct 37 ms 7252 KB Output is correct
7 Correct 24 ms 6844 KB Output is correct
8 Incorrect 115 ms 7024 KB Extra information in the output file
9 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 6952 KB Output is correct
2 Correct 305 ms 18516 KB Output is correct
3 Correct 321 ms 18560 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 6952 KB Output is correct
2 Correct 305 ms 18516 KB Output is correct
3 Correct 321 ms 18560 KB Output is correct
4 Correct 27 ms 6820 KB Output is correct
5 Correct 1286 ms 19020 KB Output is correct
6 Execution timed out 3570 ms 19268 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 6744 KB Output is correct
2 Correct 601 ms 25084 KB Output is correct
3 Correct 621 ms 25172 KB Output is correct
4 Correct 269 ms 25168 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 6744 KB Output is correct
2 Correct 601 ms 25084 KB Output is correct
3 Correct 621 ms 25172 KB Output is correct
4 Correct 269 ms 25168 KB Output is correct
5 Correct 24 ms 6748 KB Output is correct
6 Execution timed out 3563 ms 25280 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 6744 KB Output is correct
2 Correct 237 ms 17588 KB Output is correct
3 Correct 548 ms 17744 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 6744 KB Output is correct
2 Correct 237 ms 17588 KB Output is correct
3 Correct 548 ms 17744 KB Output is correct
4 Correct 22 ms 6748 KB Output is correct
5 Incorrect 574 ms 17904 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 6744 KB Output is correct
2 Correct 573 ms 25144 KB Output is correct
3 Correct 586 ms 25224 KB Output is correct
4 Correct 272 ms 25172 KB Output is correct
5 Correct 21 ms 6748 KB Output is correct
6 Correct 238 ms 17692 KB Output is correct
7 Correct 545 ms 17696 KB Output is correct
8 Correct 620 ms 18608 KB Output is correct
9 Correct 543 ms 18516 KB Output is correct
10 Correct 604 ms 20568 KB Output is correct
11 Correct 693 ms 19796 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 6744 KB Output is correct
2 Correct 573 ms 25144 KB Output is correct
3 Correct 586 ms 25224 KB Output is correct
4 Correct 272 ms 25172 KB Output is correct
5 Correct 21 ms 6748 KB Output is correct
6 Correct 238 ms 17692 KB Output is correct
7 Correct 545 ms 17696 KB Output is correct
8 Correct 620 ms 18608 KB Output is correct
9 Correct 543 ms 18516 KB Output is correct
10 Correct 604 ms 20568 KB Output is correct
11 Correct 693 ms 19796 KB Output is correct
12 Correct 24 ms 6744 KB Output is correct
13 Execution timed out 3558 ms 25244 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 6848 KB Output is correct
2 Correct 37 ms 7252 KB Output is correct
3 Correct 35 ms 7368 KB Output is correct
4 Correct 45 ms 7156 KB Output is correct
5 Correct 44 ms 7508 KB Output is correct
6 Correct 37 ms 7260 KB Output is correct
7 Correct 23 ms 6876 KB Output is correct
8 Correct 291 ms 18516 KB Output is correct
9 Correct 295 ms 18516 KB Output is correct
10 Correct 25 ms 6992 KB Output is correct
11 Correct 603 ms 25112 KB Output is correct
12 Correct 609 ms 25352 KB Output is correct
13 Correct 255 ms 25172 KB Output is correct
14 Correct 21 ms 6744 KB Output is correct
15 Correct 235 ms 17568 KB Output is correct
16 Correct 546 ms 17816 KB Output is correct
17 Correct 616 ms 18640 KB Output is correct
18 Correct 554 ms 18648 KB Output is correct
19 Correct 591 ms 20628 KB Output is correct
20 Correct 677 ms 19976 KB Output is correct
21 Correct 292 ms 18520 KB Output is correct
22 Correct 289 ms 18776 KB Output is correct
23 Correct 300 ms 19028 KB Output is correct
24 Correct 321 ms 18992 KB Output is correct
25 Correct 689 ms 20172 KB Output is correct
26 Correct 915 ms 17916 KB Output is correct
27 Correct 898 ms 18000 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 6848 KB Output is correct
2 Correct 37 ms 7252 KB Output is correct
3 Correct 35 ms 7368 KB Output is correct
4 Correct 45 ms 7156 KB Output is correct
5 Correct 44 ms 7508 KB Output is correct
6 Correct 37 ms 7260 KB Output is correct
7 Correct 23 ms 6876 KB Output is correct
8 Correct 291 ms 18516 KB Output is correct
9 Correct 295 ms 18516 KB Output is correct
10 Correct 25 ms 6992 KB Output is correct
11 Correct 603 ms 25112 KB Output is correct
12 Correct 609 ms 25352 KB Output is correct
13 Correct 255 ms 25172 KB Output is correct
14 Correct 21 ms 6744 KB Output is correct
15 Correct 235 ms 17568 KB Output is correct
16 Correct 546 ms 17816 KB Output is correct
17 Correct 616 ms 18640 KB Output is correct
18 Correct 554 ms 18648 KB Output is correct
19 Correct 591 ms 20628 KB Output is correct
20 Correct 677 ms 19976 KB Output is correct
21 Correct 292 ms 18520 KB Output is correct
22 Correct 289 ms 18776 KB Output is correct
23 Correct 300 ms 19028 KB Output is correct
24 Correct 321 ms 18992 KB Output is correct
25 Correct 689 ms 20172 KB Output is correct
26 Correct 915 ms 17916 KB Output is correct
27 Correct 898 ms 18000 KB Output is correct
28 Correct 24 ms 6748 KB Output is correct
29 Incorrect 110 ms 7244 KB Extra information in the output file
30 Halted 0 ms 0 KB -