#736284 (C++17) No.901 K-ary εxtrεεmε

提出ソース

結果

問題	No.901 K-ary εxtrεεmε
ユーザー	raven7959
提出日時	2022-02-03 10:35:15
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	371 ms / 3,000 ms
コード長	14,413 bytes
コンパイル時間	2,499 ms
コンパイル使用メモリ	229,420 KB
実行使用メモリ	31,248 KB
最終ジャッジ日時	2024-06-11 09:44:10
合計ジャッジ時間	12,939 ms
ジャッジサーバーID （参考情報）	judge5 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	138 ms 31,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	4 ms 5,376 KB
testcase_03	AC	4 ms 5,376 KB
testcase_04	AC	5 ms 5,376 KB
testcase_05	AC	4 ms 5,376 KB
testcase_06	AC	5 ms 5,376 KB
testcase_07	AC	371 ms 23,696 KB
testcase_08	AC	351 ms 23,828 KB
testcase_09	AC	353 ms 23,692 KB
testcase_10	AC	357 ms 23,692 KB
testcase_11	AC	357 ms 23,696 KB
testcase_12	AC	343 ms 23,696 KB
testcase_13	AC	352 ms 23,696 KB
testcase_14	AC	344 ms 23,824 KB
testcase_15	AC	341 ms 23,828 KB
testcase_16	AC	346 ms 23,700 KB
testcase_17	AC	307 ms 23,820 KB
testcase_18	AC	325 ms 23,708 KB
testcase_19	AC	325 ms 23,704 KB
testcase_20	AC	323 ms 23,700 KB
testcase_21	AC	315 ms 23,696 KB
testcase_22	AC	339 ms 23,692 KB
testcase_23	AC	364 ms 23,696 KB
testcase_24	AC	351 ms 23,824 KB
testcase_25	AC	345 ms 23,692 KB
testcase_26	AC	347 ms 23,824 KB
testcase_27	AC	234 ms 23,696 KB
testcase_28	AC	230 ms 23,700 KB
testcase_29	AC	229 ms 23,824 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define yn(joken) cout<<((joken) ? "Yes" : "No")<<endl
#define YN(joken) cout<<((joken) ? "YES" : "NO")<<endl
using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vd = vector<double>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvd = vector<vector<double>>;
const int INF = 1e9;
const ll LINF = 1e18;
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    for (int i = 0; i < int(v.size()); i++) {
        is >> v[i];
    }
    return is;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    for (int i = 0; i < int(v.size()); i++) {
        os << v[i];
        if (i < int(v.size()) - 1) os << ' ';
    }
    return os;
}

template <typename T = int>
struct Edge{
    int from, to;
    T cost;
    int idx;
    Edge() = default;
    Edge(int from, int to, T cost = 1, int idx = -1) : from(from), to(to), cost(cost), idx(idx) {}
    operator int() const { return to; }
};

template <typename T = int>
struct Graph{
    vector<vector<Edge<T>>> g;
    int es;
    Graph() = default;
    explicit Graph(int n) : g(n), es(0) {}
    size_t size() const{
        return g.size();
    }

    void add_directed_edge(int from, int to, T cost = 1){
        g[from].emplace_back(from, to, cost, es++);
    }

    void add_edge(int from, int to, T cost = 1){
        g[from].emplace_back(from, to, cost, es);
        g[to].emplace_back(to, from, cost, es++);
    }

    void read(int M, int padding = -1, bool weighted = false, bool directed = false){
        for (int i = 0; i < M; i++){
            int a, b;
            cin >> a >> b;
            a += padding;
            b += padding;
            T c = T(1);
            if (weighted) cin >> c;
            if (directed) add_directed_edge(a, b, c);
            else add_edge(a, b, c);
        }
    }

    inline vector<Edge<T>> &operator[](const int &k){
        return g[k];
    }

    inline const vector<Edge<T>> &operator[](const int &k) const{
        return g[k];
    }
};

template <typename T = int>
using Edges = vector<Edge<T>>;

// HeavyLightDecomposition<Graph<int>> HLD(g,root); などする,rootは指定しない場合0になる
// size: 部分木のサイズ(元の木の頂点番号->サイズ)
// depth: 深さ(元の木の頂点番号->深さ)
// down: 行きがけ順(セグ木上での順番でもある) (元の木の頂点番号->行きがけ順)
// up: 部分木クエリに使うやつ
// nxt: ある頂点が属する連結成分の中で最も浅い頂点(元の木の頂点番号->元の木の頂点番号)
// par: 親の番号(元の木の頂点番号->元の木の頂点番号)
// rev: 行きがけ順から元の木の頂点番号に戻す配列
// void path_query(int u,int v,bool vertex,F f): u,vパスについての可換なクエリを処理,頂点属性ならvertexをtrueにする
// void path_noncommutative_query(int u,int v,bool vertex,F f): u,vパスについての非可換なクエリを処理,頂点属性ならvertexをtrueにする
// void subtree_query(int u,bool vertex,F f): uを根とする部分木についてのクエリを処理
// 上3つではいずれもラムダ式でfを渡せばよく,[l,r)についての結果をどこかにまとめる感じで書くと良い
// その他,汎用的な関数がある(lca,la,dist,in_subtree,move)

template <typename G>
struct HeavyLightDecomposition{
private:
    void dfs_sz(int cur){
        size[cur] = 1;
        for (auto &dst : g[cur]){
            if (dst == par[cur]){
                if (g[cur].size() >= 2 && int(dst) == int(g[cur][0])) swap(g[cur][0], g[cur][1]);
                else continue;
            }
            depth[dst] = depth[cur] + 1;
            par[dst] = cur;
            dfs_sz(dst);
            size[cur] += size[dst];
            if (size[dst] > size[g[cur][0]]) swap(dst, g[cur][0]);
        }
    }

    void dfs_hld(int cur){
        down[cur] = id++;
        rev[down[cur]] = cur;
        for (auto dst : g[cur]){
            if (dst == par[cur]) continue;
            nxt[dst] = (int(dst) == int(g[cur][0]) ? nxt[cur] : int(dst));
            dfs_hld(dst);
        }
        up[cur] = id;
    }

    // [u, v)
    vector<pair<int, int>> ascend(int u, int v) const{
        vector<pair<int, int>> res;
        while (nxt[u] != nxt[v]){
            res.emplace_back(down[u], down[nxt[u]]);
            u = par[nxt[u]];
        }
        if (u != v) res.emplace_back(down[u], down[v] + 1);
        return res;
    }

    // (u, v]
    vector<pair<int, int>> descend(int u, int v) const{
        if (u == v) return {};
        if (nxt[u] == nxt[v]) return {{down[u] + 1, down[v]}};
        auto res = descend(u, par[nxt[v]]);
        res.emplace_back(down[nxt[v]], down[v]);
        return res;
    }

public:
    G &g;
    int id;
    vector<int> size, depth, down, up, nxt, par, rev;
    HeavyLightDecomposition(G &_g, int root = 0)
        : g(_g),
          id(0),
          size(g.size(), 0),
          depth(g.size(), 0),
          down(g.size(), -1),
          up(g.size(), -1),
          nxt(g.size(), root),
          par(g.size(), root),
          rev(g.size(), root)
    {
        dfs_sz(root);
        dfs_hld(root);
    }

    void build(int root){
        dfs_sz(root);
        dfs_hld(root);
    }

    pair<int, int> idx(int i) const { return make_pair(down[i], up[i]); }

    template <typename F>
    void path_query(int u, int v, bool vertex, const F &f){
        int l = lca(u, v);
        for (auto &&[a, b] : ascend(u, l)){
            int s = a + 1, t = b;
            s > t ? f(t, s) : f(s, t);
        }
        if (vertex) f(down[l], down[l] + 1);
        for (auto &&[a, b] : descend(l, v)){
            int s = a, t = b + 1;
            s > t ? f(t, s) : f(s, t);
        }
    }

    template <typename F>
    void path_noncommutative_query(int u, int v, bool vertex, const F &f){
        int l = lca(u, v);
        for (auto &&[a, b] : ascend(u, l)) f(a + 1, b);
        if (vertex) f(down[l], down[l] + 1);
        for (auto &&[a, b] : descend(l, v)) f(a, b + 1);
    }

    template <typename F>
    void subtree_query(int u, bool vertex, const F &f){
        f(down[u] + int(!vertex), up[u]);
    }

    int lca(int a, int b){
        while (nxt[a] != nxt[b]){
            if (down[a] < down[b]) swap(a, b);
            a = par[nxt[a]];
        }
        return depth[a] < depth[b] ? a : b;
    }

    int lca(int r, int u, int v){
        return lca(r, u) ^ lca(u, v) ^ lca(v, r);
    }

    int la(int v, int k) {
        while(1){
            int u = nxt[v];
            if(down[v] - k >= down[u]) return rev[down[v] - k];
            k -= down[v] - down[u] + 1;
            v = par[nxt[u]];
        }
    }

    int dist(int a, int b) { return depth[a] + depth[b] - depth[lca(a, b)] * 2; }

    bool in_subtree(int a, int b) { return down[a] <= down[b] && down[b] <= up[a]; }

    int move(int a, int b) {
        assert(a != b);
        return (in_subtree(b, a) ? la(b, depth[b] - depth[a] - 1) : par[a]);
    }
};

// lazy_segtree<S,op,e,F,mapping,composition,id> seg(int n)またはseg(vector<S> vec)で初期化
// Sは型, S*S->Sを返す関数 S op(S a,S b)と単位元を返す関数 S e()を設定する
// Fも形, f(x)を返す関数 S mapping(F f,S x)とf*gを返す関数 F composition(F f,F g)と単位元を返す関数 F id()を設定する 
// set(int p,S x): a[p]にxを代入する
// get(int p): a[p]を取得する
// prod(int l,int r): [l,r)をfoldした結果を返す
// all_prod(): [0,n)をfoldした結果を返す
// apply(p,f): a[p]にfを作用させる
// apply(l,r,f): [l,r)にfを作用させる
// max_right<f>(int l,G g): bool g(S x)を渡すとl以降でf(prod(l,r))=trueとなる最大のrを返す
// max_left: max_rightの逆

int ceil_pow2(int n){
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}

template <class S,
          S (*op)(S, S),
          S (*e)(),
          class F,
          S (*mapping)(F, S),
          F (*composition)(F, F),
          F (*id)()>
struct lazy_segtree{
public:
    lazy_segtree() : lazy_segtree(0) {}
    lazy_segtree(int n) : lazy_segtree(vector<S>(n, e())) {}
    lazy_segtree(const vector<S> &v) : _n(int(v.size())){
        log = ceil_pow2(_n);
        size = 1 << log;
        d = vector<S>(2 * size, e());
        lz = vector<F>(size, id());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--){
            update(i);
        }
    }

    void set(int p, S x){
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p){
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }

    S prod(int l, int r){
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return e();

        l += size;
        r += size;

        for (int i = log; i >= 1; i--){
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push(r >> i);
        }

        S sml = e(), smr = e();
        while (l < r){
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    void apply(int p, F f){
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = mapping(f, d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    void apply(int l, int r, F f){
        assert(0 <= l && l <= r && r <= _n);
        if (l == r)
            return;

        l += size;
        r += size;

        for (int i = log; i >= 1; i--){
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        {
            int l2 = l, r2 = r;
            while (l < r){
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }

        for (int i = 1; i <= log; i++){
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    template <bool (*g)(S)>
    int max_right(int l){
        return max_right(l, [](S x)
                         { return g(x); });
    }
    template <class G>
    int max_right(int l, G g){
        assert(0 <= l && l <= _n);
        assert(g(e()));
        if (l == _n) return _n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        S sm = e();
        do{
            while (l % 2 == 0) l >>= 1;
            if (!g(op(sm, d[l]))){
                while (l < size){
                    push(l);
                    l = (2 * l);
                    if (g(op(sm, d[l]))){
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*g)(S)>
    int min_left(int r){
        return min_left(r, [](S x)
                        { return g(x); });
    }
    template <class G>
    int min_left(int r, G g){
        assert(0 <= r && r <= _n);
        assert(g(e()));
        if (r == 0) return 0;
        r += size;
        for (int i = log; i >= 1; i--) push((r - 1) >> i);
        S sm = e();
        do{
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(op(d[r], sm))){
                while (r < size){
                    push(r);
                    r = (2 * r + 1);
                    if (g(op(d[r], sm))){
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

private:
    int _n, size, log;
    vector<S> d;
    vector<F> lz;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
    void all_apply(int k, F f){
        d[k] = mapping(f, d[k]);
        if (k < size) lz[k] = composition(f, lz[k]);
    }
    void push(int k){
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id();
    }
};

struct S{
    ll used,w;
};

S op(S l,S r){
    return S{l.used+r.used,l.w+r.w};
}

S e(){
    return S{0LL,0LL};
}

struct F{
    ll f;
};

S mapping(F f,S x){
    if(f.f==-1) return x;
    return S{f.f*x.w,x.w};
}

F composition(F f,F g){
    if(f.f==-1) return g;
    return f;
}

F id(){
    return F{-1LL};
}

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

    int N;
    cin>>N;
    Graph<ll> G(N);
    vector<tuple<ll,ll,ll>> E;
    rep(_,N-1){
        ll u,v,w;
        cin>>u>>v>>w;
        G.add_edge(u,v,w);
        E.emplace_back(u,v,w);
    }
    HeavyLightDecomposition<Graph<ll>> HLD(G);
    lazy_segtree<S,op,e,F,mapping,composition,id> seg(N);
    for(auto [u,v,w]:E){
        seg.set(max(HLD.down[u],HLD.down[v]),S{0,w});
    }
    int Q;
    cin>>Q;
    rep(_,Q){
        int k;
        cin>>k;
        vi V(k);
        cin>>V;
        auto f=[&](int l,int r)->void{
            seg.apply(l,r,F{1});
        };
        for(int i=1;i<k;i++){
            HLD.path_query(V[0],V[i],false,f);
        }
        cout<<seg.all_prod().used<<endl;
        seg.apply(0,N,F{0});
    }
}

yukicoder

結果

テストケース

ソースコード