結果

問題 No.898 tri-βutree
ユーザー kyawakyawa
提出日時 2021-12-09 16:22:22
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 671 ms / 4,000 ms
コード長 3,713 bytes
コンパイル時間 3,054 ms
コンパイル使用メモリ 229,028 KB
実行使用メモリ 107,712 KB
最終ジャッジ日時 2023-09-24 08:47:40
合計ジャッジ時間 17,601 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 445 ms
107,712 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 623 ms
101,236 KB
testcase_08 AC 645 ms
101,288 KB
testcase_09 AC 606 ms
101,296 KB
testcase_10 AC 617 ms
101,276 KB
testcase_11 AC 601 ms
101,404 KB
testcase_12 AC 616 ms
101,276 KB
testcase_13 AC 625 ms
101,424 KB
testcase_14 AC 625 ms
101,276 KB
testcase_15 AC 608 ms
101,148 KB
testcase_16 AC 613 ms
101,464 KB
testcase_17 AC 642 ms
101,420 KB
testcase_18 AC 622 ms
101,284 KB
testcase_19 AC 622 ms
101,268 KB
testcase_20 AC 671 ms
101,144 KB
testcase_21 AC 613 ms
101,340 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_weight(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_weight[u].push_back({v, w});
        tree_weight[v].push_back({u, w});
    }
    
    vector<long> dist(N, 0);
    vector<bool> bfs_vis(N, false); bfs_vis[0] = true;
    stack<pair<long,long>> bfs; bfs.push({0, 0});
    while(not bfs.empty()){
        auto [e, w] = bfs.top(); bfs.pop();
        for(auto [e2, w2] : tree_weight[e]){
            if(bfs_vis[e2]) continue;
            bfs_vis[e2] = true;
            dist[e2] = w + w2;
            bfs.push({e2, w + w2});
        }
    }
    
    LowestCommonAncestor lca(tree, 0);
    
    long Q; cin >> Q;
    while(Q--){
        long x, y, z; cin >> x >> y >> z;
        long dxy = dist[x] + dist[y] - 2 * dist[lca.query(x, y)];
        long dyz = dist[y] + dist[z] - 2 * dist[lca.query(y, z)];
        long dzx = dist[z] + dist[x] - 2 * dist[lca.query(z, x)];
        cout << (dxy + dyz + dzx) / 2 << '\n';
    }
}
0