結果

問題 No.901 K-ary εxtrεεmε
ユーザー yosupotyosupot
提出日時 2019-10-04 22:54:23
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 9,909 bytes
コンパイル時間 2,333 ms
コンパイル使用メモリ 229,924 KB
実行使用メモリ 15,576 KB
最終ジャッジ日時 2024-10-03 08:21:33
合計ジャッジ時間 9,701 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 1 ms
5,248 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 149 ms
12,496 KB
testcase_18 AC 144 ms
12,484 KB
testcase_19 AC 142 ms
12,640 KB
testcase_20 AC 144 ms
12,584 KB
testcase_21 AC 153 ms
12,484 KB
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 AC 124 ms
12,572 KB
testcase_28 AC 121 ms
12,604 KB
testcase_29 AC 127 ms
12,620 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx")
//#undef LOCAL
#include <bits/stdc++.h>

#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <numeric>
#include <random>
#include <set>

struct Random {
  private:
    // Use xoshiro256**
    // Refereces: http://xoshiro.di.unimi.it/xoshiro256starstar.c
    static uint64_t rotl(const uint64_t x, int k) {
        return (x << k) | (x >> (64 - k));
    }

    std::array<uint64_t, 4> s;

    uint64_t next() {
        const uint64_t result_starstar = rotl(s[1] * 5, 7) * 9;

        const uint64_t t = s[1] << 17;

        s[2] ^= s[0];
        s[3] ^= s[1];
        s[1] ^= s[2];
        s[0] ^= s[3];

        s[2] ^= t;

        s[3] = rotl(s[3], 45);

        return result_starstar;
    }

    // random choice from [0, upper]
    uint64_t next(uint64_t upper) {
        if (!(upper & (upper + 1))) {
            // b = 00..0011..11
            return next() & upper;
        }
        int lg = 63 - __builtin_clzll(upper);
        uint64_t mask = (lg == 63) ? ~0ULL : (1ULL << (lg + 1)) - 1;
        while (true) {
            uint64_t r = next() & mask;
            if (r <= upper)
                return r;
        }
    }

  public:
    Random(uint64_t seed = 0) {
        // Use splitmix64
        // Reference: http://xoshiro.di.unimi.it/splitmix64.c
        for (int i = 0; i < 4; i++) {
            uint64_t z = (seed += 0x9e3779b97f4a7c15);
            z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
            z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
            s[i] = z ^ (z >> 31);
        }
    }

    // random choice from [lower, upper]
    template <class T>
    T uniform(T lower, T upper) {
        assert(lower <= upper);
        return T(lower + next(uint64_t(upper - lower)));
    }

    bool uniform_bool() { return uniform(0, 1) == 1; }

    double uniform01() {
        uint64_t v = next(1ULL << 63);
        return double(v) / (1ULL << 63);
    }

    // generate random lower string that length = n
    std::string lower_string(size_t n) {
        std::string res = "";
        for (size_t i = 0; i < n; i++) {
            res += uniform('a', 'z');
        }
        return res;
    }

    // random shuffle
    template <class Iter>
    void shuffle(Iter first, Iter last) {
        int len = 0;
        // Reference and edit:
        // cpprefjp - C++日本語リファレンス
        // (https://cpprefjp.github.io/reference/algorithm/shuffle.html)
        for (auto it = first + 1; it != last; it++) {
            len++;
            int j = uniform(0, len);
            if (j != len)
                iter_swap(it, first + j);
        }
    }

    // generate random permutation that length = n
    template <class T>
    std::vector<T> perm(size_t n) {
        std::vector<T> idx(n);
        std::iota(idx.begin(), idx.end(), T(0));
        shuffle(idx.begin(), idx.end());
        return idx;
    }

    template <class T>
    std::vector<T> choice(size_t n, T lower, T upper) {
        assert(n <= upper - lower + 1);
        std::set<T> res;
        while (res.size() < n) res.insert(uniform(lower, upper));
        return {res.begin(), res.end()};
    }
} global_gen;

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;

#ifdef LOCAL
struct PrettyOS {
    ostream& os;
    bool first;
    template <class T> auto operator<<(T&& x) {
        if (!first) os << ", ";
        first = false;
        os << x;
        return *this;
    }
};
template <class... T> void dbg0(T&&... t) {
    (PrettyOS{cerr, true} << ... << t);
}
#define dbg(...)                                            \
    do {                                                    \
        cerr << __LINE__ << " : " << #__VA_ARGS__ << " = "; \
        dbg0(__VA_ARGS__);                                  \
        cerr << endl;                                       \
    } while (false);
#else
#define dbg(...)
#endif

template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    return os << "P(" << p.first << ", " << p.second << ")";
}

template <class T> ostream& operator<<(ostream& os, const V<T>& v) {
    os << "[";
    for (auto d : v) os << d << ", ";
    return os << "]";
}

struct LCNode {
    using NP = LCNode*;
    static NP last;
    //ll d = 0, dsm = 0;
    ll d, dsm;
    NP init_last() {
        sz = 0; // Important
        d = dsm = 0;
        return this;
    }
    void init_node(ll d) {
        sz = 1; rev = false; // Important
        this->d = dsm = d;
    }
    void update() {
        sz = 1 + l->sz + r->sz; // Important
        dsm = d + l->dsm + r->dsm;
    }
    void push() {
        assert(this != last);
        if (rev) { // Important
            if (l != last) {
                l->revdata();
            }
            if (r != last) {
                r->revdata();
            }
            rev = false;
        }
    }
    void revdata() {
        rev ^= true; swap(l, r); // Important
    }
    
    NP p, l, r;
    int sz;
    bool rev;
    LCNode() : p(nullptr), l(last), r(last) {}
    inline int pos() {
        if (p) {
            if (p->l == this) return -1;
            if (p->r == this) return 1;
        }
        return 0;
    }
    void rot() {
        NP q = p->p;
        int pps = p->pos();
        if (pps == -1) q->l = this;
        if (pps == 1) q->r = this;
        if (p->l == this) {
            p->l = r;
            if (r) r->p = p;
            r = p;
        } else {
            p->r = l;
            if (l) l->p = p;
            l = p;
        }
        p->p = this;
        p->update(); update();
        p = q;
        if (q) q->update();
    }
    void splay() {
        supush();
        int ps;
        while ((ps = pos())) {
            int pps = p->pos();
            if (!pps) {
                rot();
            } else if (ps == pps) {
                p->rot(); rot();
            } else {
                rot(); rot();
            }
        }
    }
    void expose() {
        assert(this != last);
        NP u = this, ur = last;
        do {
            u->splay();
            u->r = ur;
            u->update();
            ur = u;
        } while ((u = u->p));
        splay();
    }
    void supush() {
        if (pos()) p->supush();
        push();
    }
    void link(NP r) {
        evert(); r->expose();
        p = r;
    }
    void cut() {
        expose();
        l->p = NULL;
        l = last;
        update();
    }
    void evert() {
        expose(); revdata();
    }

    //tree func
    NP parent() {
        expose();
        NP u = this->l;
        if (u == last) return last;
        u->push();
        while (u->r != last) {
            u = u->r;
            u->push();
        }
        u->expose();
        return u;
    }

    NP root() {
        expose();
        NP u = this;
        while (u->l != last) {
            u = u->l;
            u->push();
        }
        u->expose();
        return u;
    }


    NP lca(NP n) {
        n->expose();
        expose();
        NP t = n;
        while (n->p != nullptr) {
            if (!n->pos()) t = n->p;
            n = n->p;
        }
        return (this == n) ? t : nullptr;
    }

    int dps() {
        expose();
        return sz;
    }
};
LCNode::NP LCNode::last = (new LCNode())->init_last();

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int n;
    cin >> n;
    V<LCNode> lct(2 * n - 1);        
    for (int i = 0; i < n; i++) {
        lct[i].init_node(0);
    }
    for (int i = 0; i < n - 1; i++) {
        int a, b; ll c;
        cin >> a >> b >> c;
        lct[n + i].init_node(c);
        lct[a].evert();
        lct[a].link(&(lct[n + i]));
        lct[n + i].link(&(lct[b]));
    }

    int q;
    cin >> q;
    for (int ph = 0; ph < q; ph++) {
        int ty;
        //cin >> ty;
        ty = 2;
        if (ty == 1) {
            int u, v, w; ll x;
            cin >> u >> v >> w >> x;
            lct[v].evert();
            lct[u].expose();
            auto e = lct[u].parent();
            assert(e->parent() == &(lct[v]));
            lct[u].cut();
            e->cut();
            e->init_node(x);
            lct[w].evert();
            lct[w].link(e);
            e->link(&(lct[v]));
        } else {
            function<V<int>(V<int>)> mysort = [&](V<int> v) {
                int m = int(v.size());
                global_gen.shuffle(v.begin(), v.end());
                if (m == 1) return v;
                int root = v[0];
                map<int, int> p2dps;
                map<int, V<int>> mp;
                for (int i = 0; i < m; i++) {
                    int trg = v[i];
                    auto lca = lct[root].lca(&lct[trg]);
                    int lca_id = lca - &(lct[0]);
                    if (!p2dps.count(lca_id)) {
                        p2dps[lca_id] = lct[lca_id].dps();
                    }
                    mp[p2dps[lca_id]].push_back(trg);
                }
                V<int> res;
                for (auto p: mp) {
                    mysort(p.second);
                    for (int d: p.second) res.push_back(d);
                }
                return res;
            };
            int k;
            cin >> k;
            V<int> v(k);
            for (int i = 0; i < k; i++) {
                cin >> v[i];
            }
            v = mysort(v);
            ll sm = 0;
            for (int i = 0; i < k; i++) {
                int x = v[i], y = v[(i + 1) % k];
                lct[x].evert();
                lct[y].expose();
                sm += lct[y].dsm;
//                dbg(x, y, lct[y].dsm);
            }
            cout << sm / 2 << "\n";
        }
    }
    return 0;
}
0