#685913 (C++17) No.399 動的な領主

提出ソース

結果

問題	No.399 動的な領主
ユーザー	ei1918
提出日時	2021-08-06 11:43:09
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	415 ms / 2,000 ms
コード長	10,776 bytes
コンパイル時間	2,378 ms
コンパイル使用メモリ	220,092 KB
実行使用メモリ	11,240 KB
最終ジャッジ日時	2024-09-17 00:28:01
合計ジャッジ時間	6,845 ms
ジャッジサーバーID （参考情報）	judge3 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	4 ms 5,376 KB
testcase_05	AC	32 ms 5,376 KB
testcase_06	AC	415 ms 11,116 KB
testcase_07	AC	405 ms 11,236 KB
testcase_08	AC	402 ms 11,112 KB
testcase_09	AC	395 ms 11,112 KB
testcase_10	AC	4 ms 5,376 KB
testcase_11	AC	19 ms 5,376 KB
testcase_12	AC	246 ms 11,076 KB
testcase_13	AC	231 ms 11,240 KB
testcase_14	AC	58 ms 10,984 KB
testcase_15	AC	262 ms 11,112 KB
testcase_16	AC	301 ms 10,980 KB
testcase_17	AC	395 ms 11,108 KB
testcase_18	AC	402 ms 11,040 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
bool inmap(int x, int y, int mx, int my) { return (x >= 0 && y >= 0 && x < mx && y < my); }
typedef long long ll;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pint;
typedef vector<long long> vlong;
typedef vector<string> vstring;
#define fi first
#define se second
// #define _GLIBCXX_DEBUG
#define rep(i, n) REP(i, 0, n)
#define all(v) v.begin(), v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define UPDigit(a, b) (a + b - 1) / b  //小数点切り上げ
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const int MOD = int(1e9) + 7;
const int dx[] = {1,0,-1,0,1,1,-1,-1};
const int dy[] = {0,-1,0,1,1,-1,-1,1};
#define stp(x)  setprecision(x)

// T0: 元の配列のモノイド
// T1: T0に対する作用素モノイド
template <class T0, class T1>
class BaseLinkCutTree {
    // T0上の演算、単位元
    virtual T0 f0(T0, T0) = 0;
    const T0 u0;
    // T1上の演算、単位元
    virtual T1 f1(T1, T1) = 0;
    const T1 u1;
    // T0に対するT1の作用
    virtual T0 g(T0, T1) = 0;
    // 多数のt1(T1)に対するf1の合成
    virtual T1 p(T1, int) = 0;

    struct Node {
        int idx, cnt;
        T0 val, acc;
        T1 lazy;
        Node *left, *right, *par;
        Node(int idx, T0 val, T0 u0, T1 u1)
            : idx(idx), cnt(1), val(val), lazy(u1), acc(u0), left(nullptr), right(nullptr), par(nullptr) {}
        bool is_root() { return (!par) || (par->left != this && par->right != this); }
    };

    void push(Node* t) {
        if (t->cnt < 0) {
            swap(t->left, t->right);
            if (t->left) t->left->cnt = -(t->left->cnt);
            if (t->right) t->right->cnt = -(t->right->cnt);
            t->cnt = -t->cnt;
        }
        if (t->lazy != u1) {
            t->val = g(t->val, p(t->lazy, 1));
            t->acc = g(t->acc, p(t->lazy, t->cnt));
            if (t->left) t->left->lazy = g(t->left->lazy, p(t->lazy, 1));
            if (t->right) t->right->lazy = g(t->right->lazy, p(t->lazy, 1));
            t->lazy = u1;
        }
    }

    void eval(Node* t) {
        bool flag = (t->cnt < 0);
        t->cnt = 1, t->acc = t->val;
        if (t->left) push(t->left), t->cnt += _abs(t->left->cnt), t->acc = f1(t->left->acc, t->acc);
        if (t->right) push(t->right), t->cnt += _abs(t->right->cnt), t->acc = f1(t->acc, t->right->acc);
        if (flag) t->cnt = -t->cnt;
    }

    vector<Node*> nodes;

    inline static int _abs(int val) { return val & 0x7fffffff; }
    // 回転
    void rotate(Node* u, bool right) {
        Node *p = u->par, *g = p->par;
        if (right) {
            if ((p->left = u->right)) u->right->par = p;
            u->right = p, p->par = u;
        } else {
            if ((p->right = u->left)) u->left->par = p;
            u->left = p, p->par = u;
        }
        eval(p), eval(u), u->par = g;
        if (!g) return;
        if (g->left == p) g->left = u;
        if (g->right == p) g->right = u;
        eval(g);
    }
    // uをsplay木の根にする
    void splay(Node* u) {
        while (!(u->is_root())) {
            Node *p = u->par, *gp = p->par;
            if (p->is_root()) {  // zig
                push(p), push(u);
                rotate(u, (u == p->left));
            } else {
                push(gp), push(p), push(u);
                bool flag = (u == p->left);
                if ((u == p->left) == (p == gp->left)) {  // zig-zig
                    rotate(p, flag), rotate(u, flag);
                } else {  // zig-zag
                    rotate(u, flag), rotate(u, !flag);
                }
            }
        }
        push(u);
    }
    Node* expose(Node* u) {
        Node* last = nullptr;
        for (Node* v = u; v; v = v->par) {
            splay(v);
            v->right = last;
            eval(v);
            last = v;
        }
        splay(u);
        return last;
    }
    bool connected(Node* u, Node* v) {
        expose(u), expose(v);
        return u->par;
    }
    // u(child)とv(parent)を結ぶ
    void link(Node* u, Node* v) {
        assert(!connected(u, v));
        evert(u), u->par = v;
    }
    // uと親を切り離す
    void cut(Node* u) {
        expose(u);
        assert(u->left);
        u->left->par = nullptr, u->left = nullptr, eval(u);
    }
    Node* lca(Node* u, Node* v) {
        // assert(connected(u, v));
        expose(u);
        return expose(v);
    }
    Node* get_kth(Node* v, int k) {
        expose(v);
        while (v) {
            eval(v);
            if (v->right && v->right->cnt > k) {
                v = v->right;
            } else {
                if (v->right) k -= v->right->cnt;
                if (k == 0) return v;
                k--;
                v = v->left;
            }
        }
        return nullptr;
    }
    Node* get_root(Node* v) {
        expose(v);
        while (v->left) {
            eval(v);
            v = v->left;
        }
        return v;
    }
    void evert(Node* u) { expose(u), u->cnt = -(u->cnt); }
    int depth(Node* u) {
        expose(u);
        return _abs(u->cnt) - 1;
    }
    void update(Node* u, Node* v, const T1 x) {
        evert(u), expose(v);
        v->lazy = f1(v->lazy, x), push(v);
    }
    T0 query(Node* u, Node* v) {
        evert(u), expose(v);
        return v->acc;
    }

public:
    BaseLinkCutTree(T0 u0, T1 u1) : u0(u0), u1(u1) {}
    int make_new_node(T0 v) {
        int idx = nodes.size();
        nodes.push_back(new Node(idx, v, u0, u1));
        return idx;
    }
    bool connected(int a, int b) { return connected(nodes[a], nodes[b]); }
    // uとvをつなぐ(evertせずに使える)
    void link(int u, int v) { return link(nodes[u], nodes[v]); }
    // vを親と切り離す
    void cut(int v) { return cut(nodes[v]); }
    int lca(int u, int v) { return lca(nodes[u], nodes[v])->idx; }
    // vから根にk個たどった頂点を返す。とくにget_kth(v, 0)はv
    int get_kth(int v, int k) { return get_kth(nodes[v], k)->idx; }
    int get_root(int v) { return get_root(nodes[v])->idx; }
    // vを根にもってくる
    void evert(int v) { return evert(nodes[v]); }
    int depth(int v) { return depth(nodes[v]); }
    // uvパスに現れるすべての頂点にxを作用させる
    void update(int u, int v, T1 x) { return update(nodes[u], nodes[v], x); }
    void update(int v, T1 x) { update(v, v, x); }
    // uvパスに現れるすべての頂点の累積を求める
    T0 query(int u, int v) { return query(nodes[u], nodes[v]); }
    T0 query(int v) { return query(v, v); }
};

template <class T0, class T1>
struct MinUpdateQuery : public BaseLinkCutTree<T0, T1> {
    using BaseLinkCutTree<T0, T1>::BaseLinkCutTree;
    MinUpdateQuery() : MinUpdateQuery(numeric_limits<T0>::max(), numeric_limits<T1>::min()) {}
    T0 f0(T0 x, T0 y) override { return min(x, y); }
    T1 f1(T1 x, T1 y) override { return y == numeric_limits<T1>::min() ? x : y; }
    T0 g(T0 x, T1 y) override { return y == numeric_limits<T1>::min() ? x : y; }
    T1 p(T1 x, int len) override { return x; }
};

template <class T0, class T1>
struct SumAddQuery : public BaseLinkCutTree<T0, T1> {
    using BaseLinkCutTree<T0, T1>::BaseLinkCutTree;
    SumAddQuery() : SumAddQuery(0, 0) {}
    T0 f0(T0 x, T0 y) override { return x + y; }
    T1 f1(T1 x, T1 y) override { return x + y; }
    T0 g(T0 x, T1 y) override { return x + y; }
    T1 p(T1 x, int len) override { return x * len; }
};

template <class T0, class T1>
struct MinAddQuery : public BaseLinkCutTree<T0, T1> {
    using BaseLinkCutTree<T0, T1>::BaseLinkCutTree;
    MinAddQuery() : MinAddQuery(numeric_limits<T0>::max(), 0) {}
    T0 f0(T0 x, T0 y) override { return min(x, y); }
    T1 f1(T1 x, T1 y) override { return x + y; }
    T0 g(T0 x, T1 y) override { return x + y; }
    T1 p(T1 x, int len) override { return x; }
};

template <class T0, class T1>
struct SumUpdateQuery : public BaseLinkCutTree<T0, T1> {
    using BaseLinkCutTree<T0, T1>::BaseLinkCutTree;
    SumUpdateQuery() : SumUpdateQuery(0, numeric_limits<T1>::min()) {}
    T0 f0(T0 x, T0 y) override { return x + y; }
    T1 f1(T1 x, T1 y) override { return y == numeric_limits<T1>::min() ? x : y; }
    T0 g(T0 x, T1 y) override { return y == numeric_limits<T1>::min() ? x : y; }
    T1 p(T1 x, int len) override { return x == numeric_limits<T1>::min() ? numeric_limits<T1>::min() : x * len; }
};

template <class T0>
struct SumAffineQuery : public BaseLinkCutTree<T0, pair<T0, T0>> {
    using T1 = pair<T0, T0>;  // first * x + second
    using BaseLinkCutTree<T0, T1>::BaseLinkCutTree;
    SumAffineQuery() : SumAffineQuery(0, {1, 0}) {}
    T0 f0(T0 x, T0 y) override { return x + y; }
    T1 f1(T1 x, T1 y) override { return {x.first * y.first, x.second * y.first + y.second}; }
    T0 g(T0 x, T1 y) override { return y.first * x + y.second; }
    T1 p(T1 x, int len) override { return {x.first, x.second * len}; }
    // update(i, j, {a, b}); // [i, j)にax + bを作用
    // update(i, j, {0, a}); // update
    // update(i, j, {1, a}); // 加算
    // update(i, j, {a, 0}); // 倍
};

template <class T>
struct MinmaxAffineQuery : public BaseLinkCutTree<pair<T, T>, pair<T, T>> {
    using T0 = pair<T, T>;  // {min, max}
    using T1 = pair<T, T>;  // first * x + second
    using BaseLinkCutTree<T0, T1>::BaseLinkCutTree;
    MinmaxAffineQuery()
        : MinmaxAffineQuery({numeric_limits<T>::max(), -numeric_limits<T>::max()}, {1, 0}) {
    }  // TODO: _u1を使うとコンパイル通らない原因不明
    T0 f0(T0 x, T0 y) override { return {min(x.first, y.first), max(x.second, y.second)}; }
    T1 f1(T1 x, T1 y) override { return {x.first * y.first, x.second * y.first + y.second}; }
    T0 g(T0 x, T1 y) override {
        T0 ret = {x.first * y.first + y.second, x.second * y.first + y.second};
        if (y.first < 0) swap(ret.first, ret.second);
        return ret;
    }
    T1 p(T1 x, int len) override { return x; }
    // update(i, j, {a, b}); // [i, j)にax + bを作用
    // update(i, j, {0, a}); // update
    // update(i, j, {1, a}); // 加算
    // update(i, j, {a, 0}); // 倍
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  SumAddQuery<ll, ll> lct;
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) lct.make_new_node(1);

  vint u(n);
  vint v(n);
  rep(i,n-1){
    cin>>u[i]>>v[i];
    lct.link(u[i]-1,v[i]-1);
  }

  int q;
  ll ans=0;
  cin>>q;
  rep(i,q){
    int a,b;
    cin>>a>>b;
    a--; b--;
    ans+=lct.query(a,b);
    lct.update(a,b,1);
  }

  cout<<ans<<'\n';
}

yukicoder

結果

テストケース

ソースコード