結果

問題 No.901 K-ary εxtrεεmε
ユーザー yosupotyosupot
提出日時 2019-11-16 16:22:33
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 481 ms / 3,000 ms
コード長 12,278 bytes
コンパイル時間 2,930 ms
コンパイル使用メモリ 231,220 KB
実行使用メモリ 15,440 KB
最終ジャッジ日時 2024-09-24 23:37:06
合計ジャッジ時間 12,790 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 315 ms
15,440 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 10 ms
6,940 KB
testcase_03 AC 11 ms
6,944 KB
testcase_04 AC 11 ms
6,940 KB
testcase_05 AC 11 ms
6,940 KB
testcase_06 AC 12 ms
6,940 KB
testcase_07 AC 218 ms
12,628 KB
testcase_08 AC 216 ms
12,716 KB
testcase_09 AC 216 ms
12,620 KB
testcase_10 AC 222 ms
12,752 KB
testcase_11 AC 218 ms
12,672 KB
testcase_12 AC 287 ms
12,616 KB
testcase_13 AC 286 ms
12,768 KB
testcase_14 AC 281 ms
12,620 KB
testcase_15 AC 285 ms
12,692 KB
testcase_16 AC 281 ms
12,612 KB
testcase_17 AC 165 ms
12,604 KB
testcase_18 AC 160 ms
12,680 KB
testcase_19 AC 168 ms
12,624 KB
testcase_20 AC 156 ms
12,680 KB
testcase_21 AC 158 ms
12,608 KB
testcase_22 AC 476 ms
13,132 KB
testcase_23 AC 469 ms
13,232 KB
testcase_24 AC 461 ms
13,336 KB
testcase_25 AC 471 ms
13,260 KB
testcase_26 AC 481 ms
13,232 KB
testcase_27 AC 125 ms
12,592 KB
testcase_28 AC 122 ms
12,604 KB
testcase_29 AC 129 ms
12,632 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:179:9: warning: #pragma once in main file
  179 | #pragma once
      |         ^~~~

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#pragma region template

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 Scanner {
    FILE* fp = nullptr;
    char line[1 << 15];
    size_t st = 0, ed = 0;
    void reread() {
        memmove(line, line + st, ed - st);
        ed -= st;
        st = 0;
        ed += fread(line + ed, 1, (1 << 15) - ed, fp);
    }
    bool succ() {
        while (true) {
            if (st == ed) {
                reread();
                if (st == ed) return false;
            }
            while (st != ed && isspace(line[st])) st++;
            if (st != ed) break;
        }
        if (ed - st <= 50) reread();
        return true;
    }
    template <class T, enable_if_t<is_same<T, string>::value, int> = 0>
    bool read_single(T& ref) {
        if (!succ()) return false;
        while (true) {
            succ();
            size_t sz = 1;
            while (st + sz < ed && !isspace(line[st + sz])) sz++;
            ref.append(line + st, sz);
            st += sz;
            if (st != ed) break;
        }
        return true;
    }
    template <class T, enable_if_t<is_integral<T>::value, int> = 0>
    bool read_single(T& ref) {
        if (!succ()) return false;
        bool neg = false;
        if (line[st] == '-') {
            neg = true;
            st++;
        }
        ref = T(0);
        while (isdigit(line[st])) {
            ref = 10 * ref + (line[st++] - '0');
        }
        if (neg) ref = -ref;
        return true;
    }
    template <class T> 
    bool read_single(V<T>& ref) {
        for (auto& d: ref) {
            if (!read_single(d)) return false;
        }
        return true;
    }
    void read() {}
    template <class H, class... T> void read(H& h, T&... t) {
        bool f = read_single(h);
        assert(f);
        read(t...);
    }
    Scanner(FILE* _fp) : fp(_fp) {}
};

struct Printer {
  public:
    template <bool F = false> void write() {}
    template <bool F = false, class H, class... T>
    void write(const H& h, const T&... t) {
        if (F) write_single(' ');
        write_single(h);
        write<true>(t...);
    }
    template <class... T> void writeln(const T&... t) {
        write(t...);
        write_single('\n');
    }

    Printer(FILE* _fp) : fp(_fp) {}
    ~Printer() { flush(); }

  private:
    static constexpr size_t SIZE = 1 << 15;
    FILE* fp;
    char line[SIZE], small[50];
    size_t pos = 0;
    void flush() {
        fwrite(line, 1, pos, fp);
        pos = 0;
    }
    void write_single(const char& val) {
        if (pos == SIZE) flush();
        line[pos++] = val;
    }
    template <class T, enable_if_t<is_same<T, string>::value, int> = 0>
    void write_single(const T& val) {
        for (char c : val) write_single(c);
    }
    template <class T, enable_if_t<is_integral<T>::value, int> = 0>
    void write_single(T val) {
        if (pos > (1 << 15) - 50) flush();
        if (val == 0) {
            write_single('0');
            return;
        }
        if (val < 0) {
            write_single('-');
            val = -val;  // todo min
        }
        size_t len = 0;
        while (val) {
            small[len++] = char('0' + (val % 10));
            val /= 10;
        }
        reverse(small, small + len);
        memcpy(line + pos, small, len);
        pos += len;
    }
    template <class T> void write_single(const V<T>& val) {
        auto n = val.size();
        for (size_t i = 0; i < n; i++) {
            if (i) write_single(' ');
            write_single(val[i]);
        }
    }
};

#pragma endregion

#pragma once

#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) {
        // Reference and edit:
        // cpprefjp - C++日本語リファレンス
        // (https://cpprefjp.github.io/reference/algorithm/shuffle.html)
        int len = 1;
        for (auto it = first + 1; it != last; it++) {
            len++;
            int j = uniform(0, len - 1);
            if (j != len - 1) 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;

template <class N> struct LCNode {
    using NP = LCNode*;
    using D = typename N::D;
    NP p = nullptr, l = nullptr, r = nullptr;
    int sz = 1;
    bool rev = false;
    D v = N::e_d(), sm = N::e_d();

    void single_add(D x) {
        v = N::op_dd(v, x);
        update();
    }

    void init_node(D _v) {
        v = _v;
        sm = _v;
    }
    void update() {
        sz = 1;
        if (l) sz += l->sz;
        if (r) sz += r->sz;
        sm = l ? N::op_dd(l->sm, v) : v;
        if (r) sm = N::op_dd(sm, r->sm);
    }
    void push() {
        if (rev) {
            if (l) l->revdata();
            if (r) r->revdata();
            rev = false;
        }
    }
    void revdata() {
        rev ^= true;
        swap(l, r);
    }

    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 all_push() {
        if (pos()) p->all_push();
        push();
    }
    void splay() {
        all_push();
        int ps;
        while ((ps = pos())) {
            int pps = p->pos();
            if (!pps) {
                rot();
            } else if (ps == pps) {
                p->rot();
                rot();
            } else {
                rot();
                rot();
            }
        }
    }
    void expose() {
        NP u = this, ur = nullptr;
        do {
            u->splay();
            u->r = ur;
            u->update();
            ur = u;
        } while ((u = u->p));
        splay();
    }
    void link(NP np) {
        evert();
        np->expose();
        p = np;
    }
    void cut() {
        expose();
        l->p = l = nullptr;
        update();
    }
    void evert() {
        expose();
        revdata();
    }

    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;
    }
};

struct Node {
    using D = ll;
    static D e_d() { return 0; }
    static D op_dd(const D& l, const D& r) { return l + r; }
};
int main() {
    Scanner sc(stdin);
    Printer pr(stdout);
    int n;
    sc.read(n);
    V<LCNode<Node>> lct(2 * n - 1);        
    for (int i = 0; i < n - 1; i++) {
        int a, b; ll c;
        sc.read(a, b, c);
        lct[n + i].init_node(c);
        lct[a].link(&(lct[n + i]));
        lct[n + i].link(&(lct[b]));
    }

    int q;
    sc.read(q);
    for (int ph = 0; ph < q; ph++) {
        int ty;
        //cin >> ty;
        ty = 2;
        if (ty == 1) {
        } 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 = int(lca - &(lct[0]));
                    if (!p2dps.count(lca_id)) {
                        lct[lca_id].expose();
                        p2dps[lca_id] = lct[lca_id].sz;
                    }
                    mp[p2dps[lca_id]].push_back(trg);
                }
                V<int> res;
                for (auto p: mp) {
                    p.second = mysort(p.second);
                    for (int d: p.second) res.push_back(d);
                }
                return res;
            };
            int k;
            sc.read(k);
            V<int> v(k);
            sc.read(v);
            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].sm;
//                dbg(x, y, lct[y].dsm);
            }
            pr.writeln(sm / 2);
        }
    }
    return 0;
}
0