結果

問題 No.772 Dynamic Distance Sum
ユーザー pekempeypekempey
提出日時 2018-12-20 08:50:37
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,211 ms / 5,000 ms
コード長 9,834 bytes
コンパイル時間 1,238 ms
コンパイル使用メモリ 83,400 KB
実行使用メモリ 49,200 KB
最終ジャッジ日時 2024-09-25 08:23:30
合計ジャッジ時間 18,426 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 6 ms
14,844 KB
testcase_01 AC 6 ms
15,004 KB
testcase_02 AC 5 ms
14,116 KB
testcase_03 AC 5 ms
14,576 KB
testcase_04 AC 10 ms
14,756 KB
testcase_05 AC 7 ms
15,304 KB
testcase_06 AC 9 ms
14,528 KB
testcase_07 AC 7 ms
14,692 KB
testcase_08 AC 9 ms
15,384 KB
testcase_09 AC 11 ms
15,336 KB
testcase_10 AC 9 ms
15,076 KB
testcase_11 AC 6 ms
14,816 KB
testcase_12 AC 1,211 ms
49,200 KB
testcase_13 AC 1,135 ms
47,976 KB
testcase_14 AC 686 ms
39,488 KB
testcase_15 AC 878 ms
28,824 KB
testcase_16 AC 613 ms
33,100 KB
testcase_17 AC 1,105 ms
46,628 KB
testcase_18 AC 305 ms
23,628 KB
testcase_19 AC 1,110 ms
48,140 KB
testcase_20 AC 277 ms
22,136 KB
testcase_21 AC 1,156 ms
47,504 KB
testcase_22 AC 1,048 ms
44,380 KB
testcase_23 AC 725 ms
40,744 KB
testcase_24 AC 964 ms
29,492 KB
testcase_25 AC 662 ms
33,832 KB
testcase_26 AC 996 ms
43,256 KB
testcase_27 AC 476 ms
28,208 KB
testcase_28 AC 1,045 ms
43,868 KB
testcase_29 AC 296 ms
22,772 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
   [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];
        P_COST[l] = 0;
        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;
        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]);
}

void iter(int x, vector<int> &res) {
    if (!x) return;
    res.push_back(x);
    iter(L[x], res);
    iter(R[x], res);
}

bool same(int x, int y) {
    while (P[x] != 0) x = P[x];
    while (P[y] != 0) y = P[y];
    bool res = x == y;
    global_splay(x);
    global_splay(y);
    return res;
}

long long median2(int x, int n) {
    long long res = 2e18;
    for (int i = 1; i <= n; i++) {
        if (same(i, x)) {
            global_splay(i);
            res = min(res, WD[i]);
        }
    }
    return res;
}

pair<int, long long> median(int x) {
    global_splay(x);
    int ll = 0;
    int rr = 0;
    int E = W[x];
    for (;;) {
        push(x);
        int n = W[x];
        if (L[x]) {
            int y = L[x];
            int ny = ll + W[y];
            int nx = E - ny;
            assert(ny + nx == E);
            if (ny > nx) {
                rr += W[x] - W[y];
                x = y;
                continue;
            }
        }
        if (R[x]) {
            int y = R[x];
            int ny = rr + W[y];
            int nx = E - ny;
            assert(ny + nx == E);
            if (ny > nx) {
                ll += W[x] - W[y];
                x = y;
                continue;
            }
        }
        if (q[x].size() > 0) {
            int y = q[x].min().second;
            assert(is_root(y));
            int ny = W[y];
            int nx = E - ny;
            if (ny > nx) {
                rr += ll + W[x] - W[y];
                ll = 0;
                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);
}

long long Q;

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);
            long long ans = median(a).second;
            S += ans;
            S %= n;
            printf("%lld\n", ans);
        }
    }
}
0