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

提出ソース

結果

問題	No.901 K-ary εxtrεεmε
ユーザー	Haar
提出日時	2020-05-10 20:53:42
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	355 ms / 3,000 ms
コード長	7,053 bytes
コンパイル時間	4,926 ms
コンパイル使用メモリ	224,464 KB
実行使用メモリ	26,160 KB
最終ジャッジ日時	2023-09-22 15:47:46
合計ジャッジ時間	15,065 ms
ジャッジサーバーID （参考情報）	judge12 / judge14

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	163 ms 26,160 KB
testcase_01	AC	2 ms 4,380 KB
testcase_02	AC	4 ms 4,376 KB
testcase_03	AC	3 ms 4,376 KB
testcase_04	AC	3 ms 4,380 KB
testcase_05	AC	3 ms 4,376 KB
testcase_06	AC	3 ms 4,380 KB
testcase_07	AC	234 ms 22,988 KB
testcase_08	AC	234 ms 22,900 KB
testcase_09	AC	238 ms 22,812 KB
testcase_10	AC	239 ms 22,508 KB
testcase_11	AC	233 ms 22,824 KB
testcase_12	AC	225 ms 22,876 KB
testcase_13	AC	222 ms 22,820 KB
testcase_14	AC	221 ms 22,912 KB
testcase_15	AC	220 ms 22,836 KB
testcase_16	AC	221 ms 22,996 KB
testcase_17	AC	302 ms 22,812 KB
testcase_18	AC	302 ms 22,772 KB
testcase_19	AC	301 ms 23,032 KB
testcase_20	AC	302 ms 22,852 KB
testcase_21	AC	300 ms 22,876 KB
testcase_22	AC	214 ms 22,968 KB
testcase_23	AC	218 ms 22,904 KB
testcase_24	AC	220 ms 23,244 KB
testcase_25	AC	224 ms 23,044 KB
testcase_26	AC	223 ms 23,044 KB
testcase_27	AC	341 ms 22,760 KB
testcase_28	AC	349 ms 22,784 KB
testcase_29	AC	355 ms 22,888 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>

template <typename Cost = int> class Edge{
public:
  int from,to;
  Cost cost;
  Edge() {}
  Edge(int to, Cost cost): to(to), cost(cost){}
  Edge(int from, int to, Cost cost): from(from), to(to), cost(cost){}
};

template <typename T> using Graph = std::vector<std::vector<Edge<T>>>;
template <typename T> using Tree = std::vector<std::vector<Edge<T>>>;

template <typename T, typename C> void add_edge(C &g, int from, int to, T w = 1){
  g[from].emplace_back(from, to, w);
}

template <typename T, typename C> void add_undirected(C &g, int a, int b, T w = 1){
  add_edge<T, C>(g, a, b, w);
  add_edge<T, C>(g, b, a, w);
}

template <typename T> class HLDecomposition{
  Tree<T> tree;
  int n;
  
  std::vector<int> sub, // subtree size
    par, // parent id
    head, // chain head id 
    id, // id[original id] = hld id
    rid, // rid[hld id] = original id
    next, // next node in a chain
    end; // 

  int dfs_sub(int cur, int p){
    par[cur] = p;
    int t = 0;
    for(auto &e : tree[cur]){
      if(e.to == p) continue;
      sub[cur] += dfs_sub(e.to, cur);
      if(sub[e.to] > t){
        t = sub[e.to];
        next[cur] = e.to;
        std::swap(e, tree[cur][0]);
      }
    }
    return sub[cur];
  }

  void dfs_build(int cur, int &i){
    id[cur] = i;
    rid[i] = cur;
    ++i;

    for(auto &e : tree[cur]){
      if(e.to == par[cur]) continue;
      head[e.to] = (e.to == tree[cur][0].to ? head[cur] : e.to);
      dfs_build(e.to, i);
    }

    end[cur] = i;
  }
  

public:
  HLDecomposition(const Tree<T> &tree, int root):
    tree(tree), n(tree.size()), sub(n,1), par(n,-1), head(n), id(n), rid(n), next(n,-1), end(n,-1){
    dfs_sub(root, -1);
    int i = 0;
    dfs_build(root, i);
  }

  template <typename Func> // std::function<void(int,int)>
  void path_query_vertex(int x, int y, const Func &f) const {
    while(1){
      if(id[x] > id[y]) std::swap(x, y);
      f(std::max(id[head[y]], id[x]), id[y]+1);
      if(head[x] == head[y]) return;
      y = par[head[y]];
    }
  }

  template <typename LeftFunc, typename RightFunc>
  void path_query_vertex(int x, int y, const LeftFunc &f, const RightFunc &g) const {
    const int w = lca(x, y);

    path_query_vertex(x, w, f);

    x = y;
    y = w;

    while(1){
      if(id[x] > id[y]){
        std::swap(x, y);
      }
      g(std::max({id[head[y]], id[x], id[w]+1}), id[y]+1);
      if(head[x] == head[y]) return;
      y = par[head[y]];
    }
  }

  template <typename Func> // std::function<void(int,int)>
  void path_query_edge(int x, int y, const Func &f) const {
    while(1){
      if(id[x] > id[y]) std::swap(x, y);
      if(head[x] == head[y]){
        if(x != y) f(id[x]+1, id[y]+1);
        return;
      }
      f(id[head[y]], id[y]+1);
      y = par[head[y]];
    }
  }
  
  template <typename Func> // std::function<void(int,int)>
  void subtree_query_edge(int x, const Func &f) const {
    f(id[x]+1, end[x]);
  }

  template <typename Func> // std::function<void(int,int)>
  void subtree_query_vertex(int x, const Func &f) const {
    f(id[x], end[x]);
  }

  int get_edge_id(int u, int v) const { // 辺に対応するid
    if(par[u] == v){
      return id[u];
    }else if(par[v] == u){
      return id[v];
    }
 
    return -1;
  }

  int parent(int x) const {return par[x];};

  int lca(int u, int v) const {
    while(1){
      if(id[u] > id[v]) std::swap(u, v);
      if(head[u] == head[v]) return u;
      v = par[head[v]];
    }
  }

  int get_id(int x) const {
    return id[x];
  }
};


template <typename Monoid>
class SegmentTree{
  using value_type = typename Monoid::value_type;
  
  int depth, size, hsize;
  std::vector<value_type> data;

public:
  SegmentTree(){}
  SegmentTree(int n):
    depth(n > 1 ? 32-__builtin_clz(n-1) + 1 : 1),
    size(1 << depth), hsize(size / 2),
    data(size, Monoid::id())
  {}

  inline auto operator[](int i) const {return at(i);}
  inline auto at(int i) const {return data[hsize + i];}
  
  inline auto get(int x, int y) const { // [x,y)
    value_type ret_left = Monoid::id();
    value_type ret_right = Monoid::id();
    
    int l = x + hsize, r = y + hsize;
    while(l < r){
      if(r & 1) ret_right = Monoid::op(data[--r], ret_right);
      if(l & 1) ret_left = Monoid::op(ret_left, data[l++]);
      l >>= 1, r >>= 1;
    }
    
    return Monoid::op(ret_left, ret_right);
  }

  inline void update(int i, const value_type &x){
    i += hsize;
    data[i] = x;
    while(i > 1) i >>= 1, data[i] = Monoid::op(data[i << 1 | 0], data[i << 1 | 1]);
  }

  template <typename T>
  inline void init_with_vector(const std::vector<T> &val){
    data.assign(size, Monoid::id());
    for(int i = 0; i < (int)val.size(); ++i) data[hsize + i] = val[i];
    for(int i = hsize-1; i >= 1; --i) data[i] = Monoid::op(data[i << 1 | 0], data[i << 1 | 1]);
  }

  template <typename T>
  inline void init(const T &val){
    init_with_vector(std::vector<value_type>(hsize, val));
  }  
};

template <typename T>
struct SumMonoid{
  using value_type = T;
  constexpr inline static value_type id(){return 0;}
  constexpr inline static value_type op(const value_type &a, const value_type &b){return a + b;}
};





template <typename T>
struct AuxiliaryTree{
  std::vector<int> preorder;

  void dfs(const Tree<T> &tree, int cur, int par, int &&i){
    preorder[cur] = i;
    ++i;

    for(auto &e : tree[cur]){
      if(e.to == par) continue;
      dfs(tree, e.to, cur, std::forward<int>(i));
    }
  }

  AuxiliaryTree(const Tree<T> &tree, int root){
    const int N = tree.size();
    preorder.assign(N, 0);
    dfs(tree, root, -1, 0);
  }

  template <typename LCAFunc>
  auto build(std::vector<int> vs, LCAFunc f){
    std::sort(vs.begin(), vs.end(), [&](int i, int j){return preorder[i] < preorder[j];});

    int n = vs.size();
    for(int i = 0; i < n-1; ++i){
      int x = f(vs[i], vs[i+1]);
      vs.push_back(x);
    }

    std::sort(vs.begin(), vs.end(), [&](int i, int j){return preorder[i] < preorder[j];});
    vs.erase(std::unique(vs.begin(), vs.end()), vs.end());

    return vs;
  }
};





int main(){
  int N; std::cin >> N;

  Tree<int64_t> tree(N);
  for(int i = 0; i < N-1; ++i){
    int u, v; std::cin >> u >> v;
    int64_t w; std::cin >> w;
    add_undirected(tree, u, v, w);
  }

  HLDecomposition<int64_t> hld(tree, 0);
  AuxiliaryTree<int64_t> aux(tree, 0);

  SegmentTree<SumMonoid<int64_t>> seg(N);

  for(int i = 0; i < N; ++i){
    for(auto &e : tree[i]){
      if(e.from < e.to){
        seg.update(hld.get_edge_id(e.from, e.to), e.cost);
      }
    }
  }

  int Q; std::cin >> Q;

  while(Q--){
    int k; std::cin >> k;
    std::vector<int> x(k);
    for(int i = 0; i < k; ++i) std::cin >> x[i];

    x = aux.build(x, [&](int i, int j){return hld.lca(i, j);});
    k = x.size();

    int64_t ans = 0;

    for(int i = 0; i < k; ++i){
      hld.path_query_edge(
        x[i],
        x[(i+1)%k],
        [&](int i, int j){
          ans += seg.get(i, j);
        }
      );
    }
    
    ans /= 2;
    std::cout << ans << "\n";
  }

  return 0;
}

yukicoder

結果

テストケース

ソースコード