#538389 (C++17) No.1197 モンスターショー

提出ソース

結果

問題	No.1197 モンスターショー
ユーザー	Ricky_pon
提出日時	2020-08-22 17:26:41
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	RE
実行時間	-
コード長	7,484 bytes
コンパイル時間	2,508 ms
コンパイル使用メモリ	204,204 KB
実行使用メモリ	19,584 KB
最終ジャッジ日時	2024-04-23 11:22:56
合計ジャッジ時間	16,310 ms
ジャッジサーバーID （参考情報）	judge5 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	RE	-
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	1 ms 5,376 KB
testcase_03	RE	-
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	RE	-
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	RE	-
testcase_30	RE	-
testcase_31	RE	-
testcase_32	RE	-
testcase_33	RE	-
testcase_34	RE	-
testcase_35	RE	-
testcase_36	RE	-
testcase_37	RE	-
testcase_38	RE	-
testcase_39	RE	-
testcase_40	RE	-
testcase_41	AC	2 ms 5,376 KB
testcase_42	RE	-

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

コンパイルメッセージ

main.cpp: In function 'int main()':
main.cpp:264:18: warning: 'z' may be used uninitialized [-Wmaybe-uninitialized]
  264 |             scanf("%d", z);
      |             ~~~~~^~~~~~~~~
main.cpp:261:19: note: 'z' was declared here
  261 |         int x, y, z;
      |                   ^

ソースコード

raw source code

#include <bits/stdc++.h>
#define For(i, a, b) for (int(i) = (int)(a); (i) < (int)(b); ++(i))
#define rFor(i, a, b) for (int(i) = (int)(a)-1; (i) >= (int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
T div_floor(T a, T b) {
    if (b < 0) a *= -1, b *= -1;
    return a >= 0 ? a / b : (a + 1) / b - 1;
}
template <class T>
T div_ceil(T a, T b) {
    if (b < 0) a *= -1, b *= -1;
    return a > 0 ? (a - 1) / b + 1 : a / b;
}

constexpr lint mod = 1000000007;
constexpr lint INF = mod * mod;
constexpr int MAX = 200010;

template <typename T, typename E, typename F, typename F_INV, typename G>
struct LinkCutTree {
    struct Node {
        Node *par_ptr, *left_ptr, *right_ptr;
        int idx;
        bool rev;
        T val, sum, subtree_sum;

        Node()
            : idx(-1),
              par_ptr(nullptr),
              left_ptr(nullptr),
              right_ptr(nullptr),
              rev(false),
              val(T{}),
              sum(T{}),
              subtree_sum(T{}) {}

        bool is_root() {
            return !par_ptr ||
                   (par_ptr->left_ptr != this && par_ptr->right_ptr != this);
        }

        void print_data() {
            int p = par_ptr ? par_ptr->idx : -1;
            int l = left_ptr ? left_ptr->idx : -1;
            int r = right_ptr ? right_ptr->idx : -1;
            printf(
                "id=%d, p=%d, l=%d, r=%d, rev=%d, val=%lld, sum_dist=%lld, "
                "sum_num=%lld\n",
                idx, p, l, r, rev, val.se, sum.fi, sum.se);
        }
    };

    int n;
    vector<Node> nodes;
    F f;
    F_INV f_inv;
    G g;

    LinkCutTree(int n, T et, F f, F_INV f_inv, G g)
        : n(n), f(f), f_inv(f_inv), g(g) {
        nodes.resize(n);
        rep(i, n) {
            nodes[i].idx = i;
            nodes[i].val = nodes[i].sum = nodes[i].subtree_sum = et;
        }
    }

    void toggle(Node *node) {
        if (!node->rev) return;
        if (node->left_ptr) node->left_ptr->rev ^= true;
        if (node->right_ptr) node->right_ptr->rev ^= true;
        swap(node->left_ptr, node->right_ptr);
        node->rev = false;
    }

    void pull(Node *node) {
        node->sum = node->subtree_sum;
        if (node->left_ptr) node->sum = f(node->sum, node->left_ptr->sum);
        if (node->right_ptr) node->sum = f(node->sum, node->right_ptr->sum);
        node->sum.se += node->val.se;
    }

    void rotl(Node *node) {
        Node *par = node->par_ptr, *grand_par = par->par_ptr;
        if ((par->right_ptr = node->left_ptr)) node->left_ptr->par_ptr = par;
        node->left_ptr = par;
        par->par_ptr = node;
        pull(par);
        pull(node);
        if ((node->par_ptr = grand_par)) {
            if (grand_par->left_ptr == par) grand_par->left_ptr = node;
            if (grand_par->right_ptr == par) grand_par->right_ptr = node;
            pull(grand_par);
        }
    }

    void rotr(Node *node) {
        Node *par = node->par_ptr, *grand_par = par->par_ptr;
        if ((par->left_ptr = node->right_ptr)) node->right_ptr->par_ptr = par;
        node->right_ptr = par;
        par->par_ptr = node;
        pull(par);
        pull(node);
        if ((node->par_ptr = grand_par)) {
            if (grand_par->left_ptr == par) grand_par->left_ptr = node;
            if (grand_par->right_ptr == par) grand_par->right_ptr = node;
            pull(grand_par);
        }
    }

    void toggle_all(Node *node) {
        if (node->is_root()) {
            toggle(node);
            return;
        }
        toggle_all(node->par_ptr);
        toggle(node);
    }

    void splay(int i) {
        Node *node = &nodes[i];
        toggle_all(node);
        while (!node->is_root()) {
            Node *par = node->par_ptr;
            if (par->is_root()) {
                if (par->right_ptr == node)
                    rotl(node);
                else
                    rotr(node);
                return;
            }

            Node *grand_par = par->par_ptr;
            if (par->left_ptr == node) {
                if (grand_par->left_ptr == par)
                    rotr(par), rotr(node);
                else
                    rotr(node), rotl(node);
            } else {
                if (grand_par->right_ptr == par)
                    rotl(par), rotl(node);
                else
                    rotl(node), rotr(node);
            }
        }
    }

    Node *expose(int i) {
        Node *child = nullptr;
        for (Node *par = &nodes[i]; par; par = par->par_ptr) {
            splay(par->idx);
            if (child) par->subtree_sum = f_inv(par->subtree_sum, child->sum);
            if (par->right_ptr)
                par->subtree_sum = f(par->subtree_sum, par->right_ptr->sum);
            par->right_ptr = child;
            pull(par);
            child = par;
        }
        splay(i);
        return child;
    }

    void link(int child, int par) {
        expose(child);
        expose(par);
        nodes[child].par_ptr = &nodes[par];
        nodes[par].right_ptr = &nodes[child];
        pull(&nodes[par]);
    }

    void cut(int child) {
        expose(child);
        Node *par = nodes[child].left_ptr;
        nodes[child].left_ptr = nullptr;
        par->par_ptr = nullptr;
        pull(&nodes[child]);
    }

    void evert(int i) {
        expose(i);
        nodes[i].rev = true;
        toggle(&nodes[i]);
    }

    void add_edge(int child, int par) {
        evert(par);
        evert(child);
        link(child, par);
    }

    void del_edge(int child, int par) {
        evert(par);
        cut(child);
    }

    void update_val(int i, E x) {
        evert(i);
        nodes[i].val = g(nodes[i].val, x);
        pull(&nodes[i]);
    }

    T get_subtree_sum(int child, int par) {
        evert(par);
        cut(child);
        T ret = nodes[child].sum;
        link(child, par);
        return ret;
    }
};

int main() {
    int n, K, q;
    scanf("%d%d%d", &n, &K, &q);
    int c[K];
    rep(i, K) scanf("%d", &c[i]), --c[i];
    auto f = [](pll lhs, pll rhs) {
        return make_pair(lhs.fi + rhs.fi + rhs.se, lhs.se + rhs.se);
    };
    auto f_inv = [](pll lhs, pll rhs) {
        return make_pair(lhs.fi - rhs.fi - rhs.se, lhs.se - rhs.se);
    };
    auto g = [](pll lhs, lint rhs) { return make_pair(0, lhs.se + rhs); };
    LinkCutTree<pll, lint, decltype(f), decltype(f_inv), decltype(g)> lct(
        2 * n, {0, 0}, f, f_inv, g);
    rep(_, n - 1) {
        int a, b;
        scanf("%d%d", &a, &b);
        --a;
        --b;
        lct.add_edge(a, b);
    }
    rep(i, n) lct.add_edge(i, i + n);
    rep(i, K) lct.update_val(c[i], 1);

    rep(_, q) {
        int x, y, z;
        scanf("%d%d", &x, &y);
        if (x == 1) {
            scanf("%d", z);
            --y;
            --z;
            lct.update_val(c[y], -1);
            lct.update_val(z, 1);
            c[y] = z;
        } else {
            --y;
            auto tmp = lct.get_subtree_sum(y, y + n);
            printf("%lld\n", tmp.fi);
        }
    }
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード