#305330 (C++14) No.772 Dynamic Distance Sum

提出ソース

結果

問題	No.772 Dynamic Distance Sum
ユーザー	pekempey
提出日時	2018-12-20 07:46:17
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	RE
実行時間	-
コード長	8,965 bytes
コンパイル時間	844 ms
コンパイル使用メモリ	79,720 KB
実行使用メモリ	22,764 KB
最終ジャッジ日時	2024-09-25 08:20:59
合計ジャッジ時間	9,554 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	5 ms 14,416 KB
testcase_01	AC	4 ms 14,508 KB
testcase_02	AC	4 ms 14,912 KB
testcase_03	AC	4 ms 14,352 KB
testcase_04	RE	-
testcase_05	RE	-
testcase_06	RE	-
testcase_07	RE	-
testcase_08	RE	-
testcase_09	RE	-
testcase_10	RE	-
testcase_11	RE	-
testcase_12	RE	-
testcase_13	RE	-
testcase_14	RE	-
testcase_15	RE	-
testcase_16	RE	-
testcase_17	RE	-
testcase_18	RE	-
testcase_19	RE	-
testcase_20	AC	260 ms 22,040 KB
testcase_21	RE	-
testcase_22	RE	-
testcase_23	RE	-
testcase_24	RE	-
testcase_25	RE	-
testcase_26	RE	-
testcase_27	RE	-
testcase_28	RE	-
testcase_29	AC	283 ms 22,764 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

/*
   [1] wo sankou ni shita ga (omoni median), warito tigau koto wo shita.
   Priority Queue wo tsukau to toptree wo tukawanaku temo ikeru ikeru (?)
 
   [1] S. Alstrup, J. Holm, K. D. Lichtenberg, M. Thorup. Maintaining information in fully dynamic trees with top trees, Jornal ACM Transactions on Algorithms, 1(2), Pages 243--264, 2005.
*/
#include <stdio.h>
#include <assert.h>
#include <queue> /* priority_queue */
#include <iostream>
using namespace std;

#define N 100001
#define TRUE 1
#define FALSE 0

void swap(int *x, int *y) {
    int t = *x;
    *x = *y;
    *y = t;
}

void swapl(long long *x, long long *y) {
    long long t = *x;
    *x = *y;
    *y = t;
}

struct Queue {
    std::priority_queue<std::pair<int, int>> q;
    std::priority_queue<std::pair<int, int>> q2;

    void ins(int k, int v) {
        q.emplace(k, v);
    }

    void del(int k, int v) {
        q2.emplace(k, v);
    }

    std::pair<int, int> min() {
        while (!q.empty() && !q2.empty() && q.top() == q2.top()) {
            q.pop();
            q2.pop();
        }
        return q.top();
    }

    int size() {
        return q.size() - q2.size();
    }
};

Queue q[N];

/* structure data */
int L[N], R[N], P[N], REV[N];
int MARKED[N]; /* whether the specified node is marked or not (this is a bool value) */
long long L_COST[N]; /* the cost of the downward edge */
long long R_COST[N]; /* the cost of the upward etge */
long long P_COST[N];

/* aggregation data */
int W[N]; /* the numebr of marked children */
long long WU[N]; /* the sum of weights from the external node named u to other nodes */
long long WV[N]; /* the sum of weights from the external node named v to other nodes */
long long WD[N]; /* the sum of weights from the central node to other nodes */
long long LEN[N]; /* the total length of the current cluster path */

/* special aggregation data (this data should be handled carefully !!) */
int W_DASHED[N]; /* the number of marked children lied on dashed subtrees */
long long WD_DASHED[N]; /* the sum of weights from the central node to the dashed children of the specified node */


/* external node, v is an ancestor of u */
void fix(int x) {
    W[x] = MARKED[x] + W_DASHED[x] + W[L[x]] + W[R[x]];
    WD[x] = WD_DASHED[x] + WV[L[x]] + WU[R[x]] + W[L[x]] * L_COST[x] + W[R[x]] * R_COST[x];
    WU[x] = WU[L[x]] + WU[R[x]] + WD_DASHED[x] + (LEN[L[x]] + L_COST[x]) * (MARKED[x] + W_DASHED[x]) + (LEN[L[x]] + L_COST[x] + R_COST[x]) * W[R[x]];
    WV[x] = WV[R[x]] + WV[L[x]] + WD_DASHED[x] + (LEN[R[x]] + R_COST[x]) * (MARKED[x] + W_DASHED[x]) + (LEN[R[x]] + R_COST[x] + L_COST[x]) * W[L[x]];
    LEN[x] = LEN[L[x]] + LEN[R[x]] + L_COST[x] + R_COST[x]; /* (^^) */
}

void reverse(int x, int rev) {
    if (!rev) return;
    REV[x] ^= rev;
    swapl(&WU[x], &WV[x]);
    swapl(&L_COST[x], &R_COST[x]);
    swap(&L[x], &R[x]);
}

void push(int x) {
    reverse(L[x], REV[x]);
    reverse(R[x], REV[x]);
    REV[x] = FALSE;
}

void rot(int x) {
    int y = P[x]; 
    int z = P[y];
    if (L[z] == y) L[z] = x;
    if (R[z] == y) R[z] = x;
    P_COST[x] = P_COST[y];
    P_COST[y] = 0;
    P[y] = x;
    P[x] = z;
    if (L[y] == x) {
        L[y] = R[x];
        R[x] = y;
        if (L[y]) P[L[y]] = y;
        else {
            swapl(&L_COST[y], &R_COST[x]);
        }
    } else {
        R[y] = L[x];
        L[x] = y;
        if (R[y]) P[R[y]] = y;
        else {
            swapl(&R_COST[y], &L_COST[x]);
        }
    }
    fix(y);
}

bool is_root(int x) {
    return L[P[x]] != x && R[P[x]] != x;
}

void local_splay(int x) {
    while (!is_root(x)) {
        if (!is_root(P[x])) {
            rot((L[P[x]] == x) == (L[P[P[x]]] == P[x]) ? P[x] : x);
        }
        rot(x);
    }
}

void push_ancestors(int x) {
    if (!x) return;
    push_ancestors(P[x]);
    push(x);
}

void global_splay(int x) {
    push_ancestors(x);
    {
        int y = x;
        while (y != 0) {
            while (!is_root(y)) y = P[y];
            int z = P[y];
            if (z) {
                W_DASHED[z] -= W[y];
                WD_DASHED[z] -= WV[y] + W[y] * P_COST[y];
                q[z].del(W[y], y);
            }
            y = z;
        }
    }
    int y = x;
    int l = 0;
    while (y != 0) {
        local_splay(y);
        int w = L[y];
        P_COST[w] = L_COST[y];
        L_COST[y] = P_COST[l];
        W_DASHED[y] += W[w];
        WD_DASHED[y] += WV[w] + W[w] * P_COST[w];
        if (w) {
            q[y].ins(W[w], w);
        }
        L[y] = l;
        P_COST[l] = 0;
        l = y;
        fix(y);
        y = P[y];
    }
    local_splay(x);
    fix(x);
}

void reroot(int x) {
    global_splay(x);
    reverse(x, TRUE);
    push(x);
}

void link(int x, int y, long long w) {
    reroot(x);
    global_splay(y);
    assert(L[y] == 0);
    assert(P[x] == 0);
    L[y] = x;
    P[x] = y;
    L_COST[y] = w;
    fix(y);
}

void cut(int x, int y) {
    reroot(x);
    global_splay(y);
    R_COST[y] = 0;
    P_COST[R[y]] = 0;
    P[R[y]] = 0;
    R[y] = 0;
    fix(y);
}

void dfs(int u) {
    if (!u) {
        return;
    }
    dfs(L[u]);
    // assert(!(L[u] == 0 && L_COST[u] != 0));
    // assert(!(R[u] == 0 && R_COST[u] != 0));
    printf("  ");
    printf("(%d,%lld)", L[u], L_COST[u]);
    printf("%d", u);
    printf("(%d,%lld)", R[u], R_COST[u]);
    printf("  ");
    dfs(R[u]);
}

pair<int, long long> median(int x) {
    global_splay(x);
    int n = W[x];
    for (;;) {
        if (L[x]) {
            int y = L[x];
            int m = W[y];
            if (2 * m > n) {
                x = y;
                continue;
            }
        }
        if (R[x]) {
            int y = R[x];
            int m = W[y];
            if (2 * m > n) {
                x = y;
                continue;
            }
        }
        if (q[x].size() > 0) {
            int y = q[x].min().second;
            // assert(is_root(y));
            int m = W[y];
            if (2 * m > n) {
                x = y;
                continue;
            }
        }
        break;
    }
    global_splay(x);
    return make_pair(x, WD[x]);
}

void output(int n) {
    for (int i = 1; i <= n; i++) {
        global_splay(i);
        printf("%d %lld %lld\n", i, WD[i], LEN[i]);
    }
    for (int i = 1; i <= n; i++) {
        if (is_root(i)) {
            printf("*** %d %d\n", i, P[i]);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (is_root(i)) {
            dfs(i);
        }
        puts("");
    }
}

void test1() {
    for (int i = 1; i <= 7; i++) {
        MARKED[i] = 1;
    }
    link(1, 2, 2);
    link(3, 4, 4);
    link(2, 3, 3);
    link(5, 6, 3);
    link(5, 7, 10);
    link(2, 5, 1);
    printf("%d %d %d %d %lld %lld %lld %lld\n", L[0], R[0], P[0], W[0], WD[0], WU[0], WV[0], LEN[0]);
    reroot(1);
    for (int i = 1; i <= 7; i++) {
        global_splay(i);
    }
    for (int i = 1; i <= 7; i++) {
        printf("*** %d %lld\n", i, P_COST[i]);
    }
    global_splay(7);
    for (int i = 1; i <= 7; i++) {
        if (is_root(i)) {
            dfs(i);
        }
        puts("");
    }
    global_splay(1); assert(WD[1] == 38); assert(W[1] == 7);
    global_splay(2); assert(WD[2] == 28); assert(W[2] == 7);
    global_splay(3); assert(WD[3] == 37); assert(W[3] == 7);
    global_splay(4); assert(WD[4] == 57); assert(W[4] == 7);
    global_splay(5); assert(WD[5] == 29); assert(W[5] == 7);
    global_splay(6); assert(WD[6] == 44); assert(W[6] == 7);
    global_splay(7); assert(WD[7] == 79); assert(W[7] == 7);

    cout << "---" << endl;

    cut(2, 5);
    for (int i = 1; i <= 7; i++) {
        printf("*** %d %lld\n", i, P_COST[i]);
    }
    for (int i = 1; i <= 7; i++) {
        if (is_root(i)) {
            dfs(i);
        }
        puts("");
    }
}

void test2() {
    for (int i = 1; i <= 7; i++) {
        MARKED[i] = 1;
    }
    link(1, 2, 2);
    link(3, 4, 4);
    link(2, 5, 1);
    link(5, 6, 3);
    link(5, 7, 10);
    link(2, 3, 3);
    pair<int, long long> res = median(1);
    assert(res.first == 2 && res.second == 28);
}

int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; i++) {
        MARKED[i] = TRUE;
    }
    long long S = 0;
    while (q--) {
        int type;
        scanf("%d", &type);
        if (type == 1) {
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);
            a = (a - 1 + S) % n + 1;
            b = (b - 1 + S) % n + 1;
            link(a, b, c);
        } else if (type == 2) {
            int a, b;
            scanf("%d %d", &a, &b);
            a = (a - 1 + S) % n + 1;
            b = (b - 1 + S) % n + 1;
            cut(a, b);
        } else {
            int a;
            scanf("%d", &a);
            a = (a - 1 + S) % n + 1;
            global_splay(a);
            MARKED[a] ^= 1;
            fix(a);
            auto ans = median(a);
            fix(ans.first);
            S += ans.second;
            S %= n;
            printf("%lld\n", ans.second);
        }
    }
}

yukicoder

結果

テストケース

ソースコード