結果

問題 No.901 K-ary εxtrεεmε
ユーザー kyawakyawa
提出日時 2021-12-16 20:27:28
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 591 ms / 3,000 ms
コード長 3,767 bytes
コンパイル時間 3,220 ms
コンパイル使用メモリ 233,048 KB
実行使用メモリ 104,800 KB
最終ジャッジ日時 2023-10-11 19:36:12
合計ジャッジ時間 18,253 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 323 ms
104,800 KB
testcase_01 AC 2 ms
4,352 KB
testcase_02 AC 3 ms
4,348 KB
testcase_03 AC 3 ms
4,352 KB
testcase_04 AC 3 ms
4,352 KB
testcase_05 AC 3 ms
4,352 KB
testcase_06 AC 3 ms
4,352 KB
testcase_07 AC 433 ms
100,552 KB
testcase_08 AC 432 ms
100,664 KB
testcase_09 AC 441 ms
100,356 KB
testcase_10 AC 424 ms
100,696 KB
testcase_11 AC 426 ms
100,504 KB
testcase_12 AC 415 ms
100,616 KB
testcase_13 AC 415 ms
100,480 KB
testcase_14 AC 420 ms
100,408 KB
testcase_15 AC 416 ms
100,816 KB
testcase_16 AC 425 ms
100,708 KB
testcase_17 AC 495 ms
100,416 KB
testcase_18 AC 502 ms
100,552 KB
testcase_19 AC 503 ms
100,384 KB
testcase_20 AC 485 ms
100,676 KB
testcase_21 AC 497 ms
100,676 KB
testcase_22 AC 410 ms
100,552 KB
testcase_23 AC 411 ms
100,604 KB
testcase_24 AC 406 ms
100,480 KB
testcase_25 AC 410 ms
100,548 KB
testcase_26 AC 410 ms
100,504 KB
testcase_27 AC 573 ms
100,472 KB
testcase_28 AC 591 ms
100,528 KB
testcase_29 AC 573 ms
100,508 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

template < typename Element = long >
class SparseTable{
public:
    function<Element(Element, Element)> operation;
    vector<vector<Element>> table;
    vector<long> cf;
    
    SparseTable(vector<Element>& v, Element e, function<Element(Element, Element)> operation) : operation(operation){
        long isiz = v.size();
        long jsiz = 0;
        while((1 << jsiz) <= isiz) jsiz++;
        table.resize(isiz, vector<Element>(jsiz, e));
        for(long i = 0; i < isiz; i++)table[i][0] = v[i];
        for(long j = 1; j < jsiz; j++){
            for(long i = 0; i + (1 << (j - 1)) < isiz; i++){
                table[i][j] = operation(table[i][j - 1], table[i + (1 << (j - 1))][j - 1]);
            }
        }
        cf.resize(isiz + 1);
        for(long i = 2; i <= isiz; i++) cf[i] = cf[i >> 1] + 1;
    }
    
    Element query(long l, long r/*半開区間*/){
        assert(l < r);
        long b = cf[r - l];
        return operation(table[l][b], table[r - (1 << b)][b]);
    }
};

class LowestCommonAncestor{
private:
    long N;
    vector<bool> visited;
    vector<vector<long> > Tree;
    vector<vector<long> > STtable;
    vector<long> STcf;
    
    void make_EularTour(long vis){
        EularTour.push_back(depth[vis] * N + vis);
        visited[vis] = true;
        for(auto e : Tree[vis]){
            if(visited[e]) continue;
            depth[e] = depth[vis] + 1;
            make_EularTour(e);
            EularTour.push_back(depth[vis] * N + vis);
        }
    }
    
    void make_SparseTable(){
        SparseTable<long> st(EularTour, LONG_MAX, [](long a, long b){return min(a, b);});
        STtable = st.table;
        STcf = st.cf;
    }
    
    void make_first(){
        long index = 0;
        for(auto e : EularTour){
            first_index[e % N] = min(first_index[e % N], index);
            index++;
        }
    }
public:
    vector<long> depth;
    vector<long> EularTour;
    vector<long> first_index;
    
    LowestCommonAncestor(vector<vector<long>>& tree, long root) : Tree(tree){
        N = Tree.size();
        visited.resize(N, false);
        depth.resize(N, 0);
        first_index.resize(N, INT_MAX);
        make_EularTour(root);
        make_SparseTable();
        make_first();
    }
    
    long query(long l, long r){
        long ltmp = l, rtmp = r;
        l = min(first_index[ltmp], first_index[rtmp]); r = max(first_index[ltmp], first_index[rtmp]) + 1;
        long b = STcf[r - l];
        return min(STtable[l][b], STtable[r - (1 << b)][b]) % N;
    }
};

int main(){
    long N; cin >> N;
    vector<vector<long>> tree(N);
    vector<vector<pair<long,long>>> tree_w(N);
    for(long i = 0; i < N - 1; i++){
        long u, v, w; cin >> u >> v >> w;
        tree[u].push_back(v);
        tree[v].push_back(u);
        tree_w[u].push_back({v, w});
        tree_w[v].push_back({u, w});
    }
    LowestCommonAncestor lca(tree, 0);
    vector<long> depth(N, -1);
    vector<long> dfs_order(N);
    long ord = 0;
    stack<pair<long,long>> dfs; dfs.push({0, 0});
    while(not dfs.empty()){
        auto [v, w] = dfs.top(); dfs.pop();
        depth[v] = w;
        dfs_order[v] = ord; ord++;
        for(auto [v2, w2] : tree_w[v]){
            if(depth[v2] != -1) continue;
            dfs.push({v2, w + w2});
        }
    }
    long Q; cin >> Q;
    while(Q--){
        long res = 0;
        long K; cin >> K;
        vector<long> t(K);
        for(long i = 0; i < K; i++) cin >> t[i];
        sort(t.begin(), t.end(), [&](auto a, auto b){return dfs_order[a] > dfs_order[b];});
        for(long i = 0; i < K; i++) res += depth[t[i % K]] + depth[t[(i + 1) % K]] - 2 * depth[lca.query(t[i % K], t[(i + 1) % K])];
        cout << res / 2 << '\n';
    }
}
0