제출 #1042410

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1042410		sleepntsheep	Inside information (BOI21_servers)	C11	50 / 100	3575 ms	30592 KiB

servers

        #include <stdio.h>
        #include <stdlib.h>
         
        #define N 120001
        #define B 700
         
         int max(int i, int j) {return i > j ? i : j;}

        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] = max(dp[qq[i].a], y + 1);
        dp[qq[i].b] = max(dp[qq[i].b], x + 1);
            }
         
            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') {
                    if (j % B == 0) {
                        build(map_time[j], j);
                        at = map_time[j] + 1;
                    }
                    ++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);
                }
            }
        }
         

컴파일 시 표준 에러 (stderr) 메시지

servers.c: In function 'pus_':
servers.c:14:34: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   14 |             else if (0 == (o & o - 1)) eh[i] = (int*)realloc(eh[i], 2 * o * sizeof **eh);
      |                                ~~^~~
servers.c: In function 'main':
servers.c:111:13: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |             scanf("%d%d", &n, &q);
      |             ^~~~~~~~~~~~~~~~~~~~~
servers.c:117:17: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |                 scanf(" %c%d", &c, &a);
      |                 ^~~~~~~~~~~~~~~~~~~~~~
servers.c:119:21: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |                     scanf("%d", &b);
      |                     ^~~~~~~~~~~~~~~
servers.c:123:21: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |                     scanf("%d", &b);
      |                     ^~~~~~~~~~~~~~~

• Subtask 1: 2.5 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 5
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 0 / 17.5