yukicoder No.529 - 帰省ラッシュ

Source

ニコニコミュニティ
問題文

問題概要

$N$ 個ノードと $M$ 個の枝からなる連結な無向グラフが与えられる．
以下のどちらかの形式の $Q$ 個のクエリが与えられる．

  1. $1$ $x$ $y$ : ノード $x$ に価値 $y$ の獲物が出現する
  2. $2$ $x$ $y$ : ノード $x$ からノード $y$ まで，同じ枝を $2$ 回以上通らないようにして移動する．その際，通ったノードにいる獲物は1匹まで捕まえられるとして，捕まえられる獲物のうち最も価値の高い獲物を $1$ 匹捕まえて移動する．捕まえた獲物は居なくなる．また捕まえられる獲物が居ない場合は捕まえずに移動する．

後者のクエリが来るたびに，捕まえた獲物の価値（もしくは捕まえられなかったこと）を出力する問題．

解法

グラフを二重辺連結成分分解し，二重辺連結成分からなる木を構成する．
すると，移動するクエリにおいて，通る二重辺連結成分は一意に定まり，その連結成分の中のノードは全て訪れることができる．
よって，その木の各ノードにその連結成分に含まれる獲物の価値の最大値をもたせ，
Heavy Light Decompositionなどを行い，その木上のパスの最大値の場所を高速に求められるようにしておく．
各連結成分に出現している獲物の価値の情報はpriority_queueなどで管理すれば良い．
時間計算量は $O(N+M+Q (\log N)^2 + Q\log Q)$ 程度．

cLay（version 2017628-1）のコード

C++に変換後のコードはこちら

int N, M, Q;
int A[200000], B[200000];
int X, Y, Z;

int tn;
int cnv[100000];
int val[100000];
priority_queue<int> q[100000];
{
  int i, j, k;
  graph og, g;
  HLD hld;
  HLD_segtree<int> t;
  
  rd(N,M,Q,(A,B)(M));
  A[0..M-1]--;
  B[0..M-1]--;
  og.setEdge(N,M,A,B);
  tn = og.bcc(cnv);
  g = og.reduce(tn, cnv);

  val[0..tn-1] = 1;
  hld.init(g);
  t.init(&hld, val);
  val[0..tn-1] = -1;

  while(Q--){
    rd(X,Y,Z);
    if(X==1){
      Y = cnv[Y-1];
      q[Y].push(Z);
      if(val[Y] < Z){
        val[Y] = Z;
        t.change(Y,Y,-Z);
      }
    } else {
      Y = cnv[Y-1];
      Z = cnv[Z-1];
      k = t.getMinInd(Y, Z);
      wt(val[k]);
      if(val[k]==-1) continue;
      q[k].pop();
      if(q[k].size()) Z = q[k].top(); else Z = -1;
      val[k] = Z;
      t.change(k,k,-Z);
    }
  }
}

Current time: 2024年04月19日10時55分01秒
Last modified: 2017年06月28日23時18分14秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン：