#178918 (C++14) No.529 帰省ラッシュ

提出ソース

結果

問題	No.529 帰省ラッシュ
ユーザー	koyumeishi
提出日時	2017-06-09 23:37:08
言語	C++14 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	779 ms / 4,500 ms
コード長	11,494 bytes
コンパイル時間	2,496 ms
コンパイル使用メモリ	146,264 KB
実行使用メモリ	48,240 KB
最終ジャッジ日時	2023-08-22 10:31:54
合計ジャッジ時間	12,482 ms
ジャッジサーバーID （参考情報）	judge15 / judge12

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,376 KB
testcase_01	AC	2 ms 4,380 KB
testcase_02	AC	1 ms 4,380 KB
testcase_03	AC	1 ms 4,376 KB
testcase_04	AC	9 ms 4,376 KB
testcase_05	AC	9 ms 4,376 KB
testcase_06	AC	9 ms 4,380 KB
testcase_07	AC	9 ms 4,380 KB
testcase_08	AC	609 ms 30,964 KB
testcase_09	AC	613 ms 31,536 KB
testcase_10	AC	646 ms 38,440 KB
testcase_11	AC	648 ms 38,604 KB
testcase_12	AC	567 ms 27,556 KB
testcase_13	AC	550 ms 48,240 KB
testcase_14	AC	624 ms 32,812 KB
testcase_15	AC	766 ms 39,336 KB
testcase_16	AC	779 ms 39,384 KB
testcase_17	AC	732 ms 41,660 KB
testcase_18	AC	716 ms 41,832 KB
testcase_19	AC	719 ms 39,544 KB

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

ソースコード

raw source code

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <functional>
#include <set>
#include <ctime>
#include <random>
#include <chrono>
#include <cassert>
#include <tuple>
#include <utility>
using namespace std;

namespace {
  using Integer = long long; //__int128;
  template<class T, class S> istream& operator >> (istream& is, pair<T,S>& p){return is >> p.first >> p.second;}
  template<class T> istream& operator >> (istream& is, vector<T>& vec){for(T& val: vec) is >> val; return is;}
  template<class T> istream& operator ,  (istream& is, T& val){ return is >> val;}
  template<class T, class S> ostream& operator << (ostream& os, const pair<T,S>& p){return os << p.first << " " << p.second;}
  template<class T> ostream& operator << (ostream& os, const vector<T>& vec){for(size_t i=0; i<vec.size(); i++) os << vec[i] << (i==vec.size()-1?"":" "); return os;}
  template<class T> ostream& operator ,  (ostream& os, const T& val){ return os << " " << val;}

  template<class H> void print(const H& head){ cout << head; }
  template<class H, class ... T> void print(const H& head, const T& ... tail){ cout << head << " "; print(tail...); }
  template<class ... T> void println(const T& ... values){ print(values...); cout << endl; }

  template<class H> void eprint(const H& head){ cerr << head; }
  template<class H, class ... T> void eprint(const H& head, const T& ... tail){ cerr << head << " "; eprint(tail...); }
  template<class ... T> void eprintln(const T& ... values){ eprint(values...); cerr << endl; }

  class range{ Integer start_, end_, step_; public: struct range_iterator{ Integer val, step_; range_iterator(Integer v, Integer step) : val(v), step_(step) {} Integer operator * (){return val;} void operator ++ (){val += step_;} bool operator != (range_iterator& x){return step_ > 0 ? val < x.val : val > x.val;} }; range(Integer len) : start_(0), end_(len), step_(1) {} range(Integer start, Integer end) : start_(start), end_(end), step_(1) {} range(Integer start, Integer end, Integer step) : start_(start), end_(end), step_(step) {} range_iterator begin(){ return range_iterator(start_, step_); } range_iterator   end(){ return range_iterator(  end_, step_); } };

  inline string operator "" _s (const char* str, size_t size){ return move(string(str)); }
  constexpr Integer my_pow(Integer x, Integer k, Integer z=1){return k==0 ? z : k==1 ? z*x : (k&1) ? my_pow(x*x,k>>1,z*x) : my_pow(x*x,k>>1,z);}
  constexpr Integer my_pow_mod(Integer x, Integer k, Integer M, Integer z=1){return k==0 ? z%M : k==1 ? z*x%M : (k&1) ? my_pow_mod(x*x%M,k>>1,M,z*x%M) : my_pow_mod(x*x%M,k>>1,M,z);}
  constexpr unsigned long long operator "" _ten (unsigned long long value){ return my_pow(10,value); }

  inline int k_bit(Integer x, int k){return (x>>k)&1;} //0-indexed

  mt19937 mt(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count());

  template<class T> string join(const vector<T>& v, const string& sep){ stringstream ss; for(size_t i=0; i<v.size(); i++){ if(i>0) ss << sep; ss << v[i]; } return ss.str(); }

  inline string operator * (string s, int k){ string ret; while(k){ if(k&1) ret += s; s += s; k >>= 1; } return ret; }
}
constexpr long long mod = 9_ten + 7;
struct edge{
  int to;
  int id;
};

class Bridge{
  int size;
  vector<vector<edge>> G;
  vector<int> v;
  vector<bool> is_bridge;
  int num_bridge;
public:

  vector<pair<int,int>> bridge;
  vector<int> component;
  vector<vector<int>> new_Graph;

  //pre-calc
  void first_dfs(int pos, vector<bool>& visit, vector<bool>& used){
    if(visit[pos]){
      v[pos]--;
      return;
    }

    visit[pos] = true;
    for(int i=0; i<G[pos].size(); i++){
      edge& next = G[pos][i];
      if(used[next.id]) continue;
      if(visit[next.to]) v[pos]++;

      used[next.id] = true;
      first_dfs(next.to, visit, used);
    }
  }

  //imos finding-bridge
  int second_dfs(int pos, vector<bool>& visit){
    visit[pos] = true;

    int ret = v[pos];
    for(int i=0; i<G[pos].size(); i++){
      int next = G[pos][i].to;
      if(visit[next]) continue;

      int tmp = second_dfs(next, visit);
      ret += tmp;
      if(tmp == 0){
        is_bridge[G[pos][i].id] = true;
        num_bridge++;
        bridge.push_back({pos, next});
      }
    }

    return ret;
  }

  //get components that each node belong to
  void third_dfs(int pos, int c, vector<bool>& visit){
    visit[pos] = true;

    for(int i=0; i<G[pos].size(); i++){
      edge& next = G[pos][i];
      if(is_bridge[next.id]) continue;
      if(visit[next.to]) continue;
      third_dfs(next.to, c, visit);
    }

    component[pos] = c;
  }


  Bridge(vector<vector<edge>>& g, int e_size) : 
    G(g),
    size(g.size()),
    v(g.size()),
    is_bridge(e_size, false),
    num_bridge(0)
  {
    vector<bool> visit(size, false);
    vector<bool> used(e_size, false);

    for(int i=0; i<size; i++){
      if(visit[i]) continue;
      first_dfs(i, visit, used);
    }

    fill(visit.begin(), visit.end(), false);
    for(int i=0; i<size; i++){
      if(visit[i]) continue;
      second_dfs(i, visit);
    }


    component.resize(size, -1);
    
    fill(visit.begin(), visit.end(), false);
    int num_components = 0;
    for(int i=0; i<size; i++){
      if(visit[i]) continue;
      third_dfs(i, num_components, visit);
      num_components++;
    }

    //decomposited graph
    //this is a "forest"
    new_Graph.resize(num_components);
    for(int i=0; i<bridge.size(); i++){
      int u = bridge[i].first;
      int v = bridge[i].second;
      new_Graph[component[u]].push_back(component[v]);
      new_Graph[component[v]].push_back(component[u]);
    }
  }
};

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]};
  }
};

template<class Value = int>
class SegmentTree{
  int n;
  vector<Value> V;
  Value DEFAULT_VALUE;

  //evaluation function
  static Value default_evaluate(Value a, Value b){
    return max(a,b);
  }

  function< Value(Value, Value) > evaluate;

  //return evaluated value in [a,b)
  //T[at] covers [l,r)
  Value RangeEvaluation(int a, int b, int at, int l, int r){
    //out of range
    if(r <= a || b <= l) return DEFAULT_VALUE;
    //covered
    if(a <= l && r <= b) return V[at];

    //partially covered
    else{
      Value val_left = RangeEvaluation(a,b, at*2+1, l, (l+r)/2);
      Value val_right = RangeEvaluation(a,b, at*2+2, (l+r)/2, r);
      return evaluate(val_left, val_right);
    }
  }

 public:
  SegmentTree(int size, Value DEFAULT = 0, function< Value(Value, Value) > eval = default_evaluate){
    DEFAULT_VALUE = DEFAULT;
    evaluate = eval;
    n=1;
    while(n<size) n <<= 1;
    V = vector<Value>(2*n - 1, DEFAULT_VALUE);
  }

  void update(int at, Value new_val){
    at += n-1;
    V[at] = new_val;
    while(at>0){
      at = (at-1)/2;
      V[at] = evaluate(V[at*2 + 1], V[at*2 + 2]);
    }
  }


  //return evaluated value in [l,r)
  Value RangeEvaluation(int l, int r){
    if(l>=r) return DEFAULT_VALUE;
    if(l>=n) return DEFAULT_VALUE;
    return RangeEvaluation(l,r, 0, 0, n);
  }
};

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,m,q;
  cin >> n,m,q;

  vector<vector<edge>> G(n);
  for(int i : range(m)){
    int a,b;
    cin >> a,b;
    a--; b--;
    G[a].push_back( edge{b, i} );
    G[b].push_back( edge{a, i} );
  }

  Bridge B(G, m);

  vector<vector<int>>& g = B.new_Graph;
  vector<int>& c = B.component;
  vector<priority_queue<int>> z(g.size());

  HeavyLightDecomposition h(g);
  
  vector<SegmentTree<int>> seg;
  seg.reserve(h.S.size());
  for(int i=0; i<h.S.size(); i++){
    seg.emplace_back( h.S[i].element.size() );
  }

  map<int, int> memo;
  for(int i=0; i<q; i++){
    int t;
    cin >> t;
    if(t==1){
      int u,w;
      cin >> u,w;
      u--;

      u = c[u];

      memo[w] = u;

      z[ u ].push(w);
      auto p = h.get_position( u );
      int s_i = p.first;
      int e_i = p.second;

      seg[s_i].update( e_i, z[u].top() );

    }else if(t==2){
      int s,t;
      cin >> s,t;
      s--; t--;

      s = c[s];
      t = c[t];

      int p = LCA(h, s,t);

      int mx = 0;
      for(int j=0; j<2; j++){
        while(h.get_position(s).first != h.get_position(p).first){
          auto pp = h.get_position(s);
          auto s_i = pp.first;
          auto e_i = pp.second;
          int tmp = seg[s_i].RangeEvaluation(0, e_i+1);
          mx = max(mx, tmp);

          s = h.S[s_i].parent_vertex;
        }
        {
          auto ps = h.get_position(s);
          auto pp = h.get_position(p);
          int tmp = seg[ps.first].RangeEvaluation( pp.second, ps.second+1 );
          mx = max(mx, tmp);
        }
        swap(s,t);
      }

      if(mx == 0){
        println(-1);
      }else{
        int u = memo[mx];
        z[u].pop();
        auto p = h.get_position( u );
        int s_i = p.first;
        int e_i = p.second;
        seg[s_i].update( e_i, z[u].size()==0 ? 0 : z[u].top() );

        println(mx);
      }

    }else{
      println("unko");
      abort();
    }
  }


  return 0;
}

yukicoder

結果

テストケース

ソースコード