#103178 (C++14) No.399 動的な領主

提出ソース

結果

問題	No.399 動的な領主
ユーザー	koyumeishi
提出日時	2016-07-13 05:23:40
言語	C++14 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	421 ms / 2,000 ms
コード長	8,549 bytes
コンパイル時間	1,211 ms
コンパイル使用メモリ	96,956 KB
実行使用メモリ	34,508 KB
最終ジャッジ日時	2023-08-07 14:23:39
合計ジャッジ時間	6,121 ms
ジャッジサーバーID （参考情報）	judge15 / judge11

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,376 KB
testcase_01	AC	2 ms 4,380 KB
testcase_02	AC	2 ms 4,380 KB
testcase_03	AC	1 ms 4,376 KB
testcase_04	AC	3 ms 4,376 KB
testcase_05	AC	28 ms 5,764 KB
testcase_06	AC	421 ms 28,244 KB
testcase_07	AC	415 ms 28,388 KB
testcase_08	AC	397 ms 29,568 KB
testcase_09	AC	391 ms 29,332 KB
testcase_10	AC	4 ms 4,376 KB
testcase_11	AC	20 ms 6,196 KB
testcase_12	AC	247 ms 34,480 KB
testcase_13	AC	232 ms 34,508 KB
testcase_14	AC	146 ms 33,956 KB
testcase_15	AC	241 ms 34,012 KB
testcase_16	AC	255 ms 33,712 KB
testcase_17	AC	401 ms 29,168 KB
testcase_18	AC	397 ms 29,236 KB

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

ソースコード

raw source code

#include <iostream>
#include <vector>
#include <cassert>
#include <functional>
#include <algorithm>
using namespace std;

template<class T=int>
class Segment_Tree_Lazy{
private:
  //default values are set in the constractor
  const T default_value;    //default (NULL) node value
  const T default_lazy_value; //default lazy value

  struct node{
    T value; T lazy_value;
    bool lazy; int lb; int ub;
    node* par; node* lch; node* rch;

    node(T default_value, T default_lazy_value) : 
      value(default_value),
      lazy_value(default_lazy_value),
      lazy(false),
      lb(0),ub(0),      //this node covers [lb, rb)
      par(NULL),lch(NULL),rch(NULL){
    }
  };

  T evaluate(T left_val, T right_val){  //evaluate node value
    return left_val + right_val;  //sum
    //return max(left_val, right_val);  //max
  }

  T evaluate_node_and_lazy(T node_val, T lazy_val){ //evaluate node value and lazy value
    return node_val + lazy_val; //sum
    //return max(node_val, lazy_val); //max
    //return lazy_val;  //fill
  }
  T evaluate_lazy_and_lazy(T old_val, T new_val){ 
    return old_val + new_val; //sum
    //return new_val;   //fill
  }

  void new_lazy(node* t, T add_value){  
    if(t==NULL) return;
    if(t->lazy){
      t->lazy_value = evaluate_lazy_and_lazy(t->lazy_value, add_value);
    }else{
      t->lazy_value = add_value;
    }
    t->lazy = true;
  }

  T lazy_to_value(node* t){
    if(t->lazy) return t->lazy_value * (t->ub - t->lb);
    return default_lazy_value;
  }

  T get_value(node* t){
    if(t==NULL) return default_value;
    return evaluate_node_and_lazy(t->value , lazy_to_value(t));
  }

  vector<node> v;
  node* root;

  int size;

  node* constract(node* t, int pos, int lb, int ub){
    if(pos == 0){
      t->par = t;
    }
    t->lb = lb;
    t->ub = ub;

    if(pos<size-1){
      t->lch = constract(&v[(pos<<1) + 1], (pos<<1) + 1, lb, (ub+lb)>>1);
      t->lch->par = t;

      t->rch = constract(&v[(pos<<1) + 2], (pos<<1) + 2, (ub+lb)>>1, ub);
      t->rch->par = t;
    }

    return t;
  }

  void initialize(int size_){
    size = 1;
    while(size < size_) size <<= 1;

    v = vector<node>(size<<1, node(default_value, default_lazy_value));
    root = constract(&v[0], 0, 0, size);
  }

  //propagate lazy value of node t to its children
  void push(node* t){
    if(t==NULL) return;
    if(t->lazy){
      if(t->lch != NULL){ //has child
        new_lazy(t->lch, t->lazy_value);
        new_lazy(t->rch, t->lazy_value);

        t->value = evaluate( get_value(t->lch), get_value(t->rch) );
      }else{
        t->value = get_value(t);
      }

      t->lazy_value = default_lazy_value;
      t->lazy = false;
    }
  }


  void range_add(int left, int right, T add_value, node* t){
    if(t==NULL) return;
    if(t->ub <= left || right <= t->lb){
      return;
    }

    push(t);
    if(left <= t->lb && t->ub <= right){
      new_lazy(t, add_value);
      return;
    }

    //partialy covered
    range_add(left, right, add_value, t->lch);
    range_add(left, right, add_value, t->rch);
    
    t->value = evaluate( get_value(t->lch), get_value(t->rch) );
  }

  //get value of [left,right)
  T get_range_value(int left, int right, node* t){
    if(t==NULL) return default_value;
    if(t->ub <= left || right <= t->lb){
      return default_value;
    }

    push(t);
    if(left <= t->lb && t->ub <= right){
      return get_value(t);
    }

    T L = get_range_value(left, right, t->lch);
    T R = get_range_value(left, right, t->rch);

    return evaluate(L, R);
  }

  void lazy_update(node* t){
    if(t->par != root){
      lazy_update(t->par);
    }
    push(t);
  }

public:
  //default node value must be set
  // sum : 0
  // max : MIN_INF
  // min : MAX_INF
  // gcd : 1
  Segment_Tree_Lazy(int size_, T default_value__ = 0, T default_lazy_value__ = 0) : 
    default_value(default_value__), default_lazy_value(default_lazy_value__){
    initialize(size_);
  }


  //node[pos] <= new_value
  void update(int pos, T new_value){
    node* t = &v[pos + size-1];
    
    lazy_update(t);

    t->value = new_value;

    while(t != root){
      t = t->par;
      t->value = evaluate( get_value(t->lch), get_value(t->rch) );
    }
  }

  //[l,r) += add_value
  void range_add(int left, int right, T add_value){
    range_add(left, right, add_value, root);
  }

  //get value [left,right)
  T get_range_value(int left, int right){
    return get_range_value(left, right, root);
  }

  void dbg(){
    for(int i=0; i<v.size(); i++){
      cerr << get_value(&v[i]) << " ";
    }
    cerr << endl;
  }
};

//HL分解 構築O(|v|), 空間O(|v|)
class HeavyLightDecomposition{
 public:
  struct heavy_set{
    vector<int> element;
    int depth;
    int parent_vertex;
    heavy_set(int v, int d, int par) : element(1,v), depth(d), parent_vertex(par){}
  };

  vector<vector<int>>& G;
  vector<heavy_set> S;
  vector<int> subtree_size;
  vector<int> set_index;
  vector<int> ele_index;

 private:
  int get_subtree_size(int pos, int par){
    int sz = 1;
    for(int ch : G[pos]){
      if(ch == par) continue;
      sz += get_subtree_size(ch, pos);
    }
    return subtree_size[pos] = sz;
  }

  void make_path(int pos, int par, int set_id){
    set_index[pos] = set_id;
    ele_index[pos] = S[set_id].element.size()-1;

    int largest_child = -1;
    int value = 0;

    for(int ch : G[pos]){
      if(ch == par) continue;
      if(value < subtree_size[ch]){
        value = subtree_size[ch];
        largest_child = ch;
      }
    }

    for(int ch : G[pos]){
      if(ch == par) continue;
      if(largest_child == ch){
        S[set_id].element.push_back(ch);
        make_path(ch, pos, set_id);
      }else{
        S.emplace_back( ch, S[set_id].depth+1, pos );
        make_path(ch, pos, S.size()-1);
      }
    }
  }

  void init(int root){
    subtree_size.resize(G.size(), 0);
    get_subtree_size(root,root);

    set_index.resize(G.size(), 0);
    ele_index.resize(G.size(), 0);

    S.emplace_back( root,0,root );

    make_path( root, root, 0 );

    subtree_size.clear();
  }

 public:
  HeavyLightDecomposition(vector<vector<int>>& G_, int root = 0) : G(G_){
    init(root);
  }

  //set_index, element_index
  //S[set_index].element[element_index] == v
  pair<int,int> get_position(int v){
    return {set_index[v], ele_index[v]};
  }
};

//Lowest Common Ancestor with HL-decomposition tree
//O(log n) / query
int LCA(HeavyLightDecomposition& T, int u, int v){
  auto pu = T.get_position(u);
  auto pv = T.get_position(v);
  if(pu.first == pv.first){
    return pu.second < pv.second ? u : v;
  }

  if(T.S[pu.first].depth > T.S[pv.first].depth){
    swap(pu, pv);
    swap(u,v);
  }

  while(T.S[pu.first].depth != T.S[pv.first].depth){
    v = T.S[pv.first].parent_vertex;
    pv = T.get_position( v );
  }

  while(pu.first != pv.first){
    u = T.S[pu.first].parent_vertex;
    v = T.S[pv.first].parent_vertex;
    pu = T.get_position(u);
    pv = T.get_position(v);
    if(T.S[pv.first].depth == 0) break;
    if(T.S[pv.first].depth == 0) break;
  }

  if(pu.first == pv.first){
    return pu.second < pv.second ? u : v;
  }else{
    abort();
  }
  return -1;
}

int main(){
  int n;
  cin >> n;
  vector<vector<int>> G(n);
  for(int i=0; i<n-1; i++){
    int u,v;
    cin >> u >> v;
    u--; v--;
    G[u].push_back(v);
    G[v].push_back(u);
  }

  HeavyLightDecomposition t(G, 0);

  vector<Segment_Tree_Lazy<long long>> seg;
  seg.reserve( t.S.size() );
  for(int i=0; i<t.S.size(); i++){
    seg.emplace_back( t.S[i].element.size() );
  }

  long long ans = 0;

  int q;
  cin >> q;
  while(q--){
    int u,v;
    cin >> u >> v;
    u--; v--;

    int p = LCA(t, u,v);

    while( t.get_position(u).first != t.get_position(p).first ){
      auto tmp = t.get_position(u);
      seg[ tmp.first ].range_add(0, tmp.second+1, 1);
      ans += seg[ tmp.first ].get_range_value(0, tmp.second+1);

      u = t.S[ tmp.first ].parent_vertex;
    }

    while( t.get_position(v).first != t.get_position(p).first ){
      auto tmp = t.get_position(v);
      seg[ tmp.first ].range_add(0, tmp.second+1, 1);
      ans += seg[ tmp.first ].get_range_value(0, tmp.second+1);

      v = t.S[ tmp.first ].parent_vertex;
    }

    auto tmp_u = t.get_position(u);
    auto tmp_v = t.get_position(v);
    seg[tmp_u.first].range_add( min(tmp_u.second, tmp_v.second), max(tmp_u.second, tmp_v.second)+1, 1);
    ans += seg[tmp_u.first].get_range_value( min(tmp_u.second, tmp_v.second), max(tmp_u.second, tmp_v.second)+1 );

  }

  cout << ans << endl;

  return 0;
}

yukicoder

結果

テストケース

ソースコード