保存されている過去のバージョンの一覧

パ研合宿2019　第4日「Teamwork」 F問題 - イーハチはやる

Source

パ研合宿2019　第4日「Teamwork」
問題文

問題概要

省略

解法

省略

cLay（version 20191227-1）のコード

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

int N, K, A[2d5], B[2d5], C[2d5], Q, S, T;
wgraph<int> g;
HLD hld;

int ord[2d5], dep[2d5];
int up1[2d5][18], up2[2d5][18];
ll costHP[2d5][18];

ll getCostHP(int i, int s){
  ll res = 0;
  rep(k,18) if(s&1<<k){
    if(up1[i][k]==-1) return ll_inf;
    res += costHP[i][k];
    i = up1[i][k];
  }
  return res;
}

pair<int,int> getCost(int i, int s){
  int j, k;
  pair<int,int> res = make_pair(0,0);
  rrep(k,18){
    if(up2[i][k]==-1) continue;
    if(dep[up2[i][k]] >= dep[i]-s){
      j = up2[i][k];
      res.first += (1<<k);
      s -= dep[i] - dep[j];
      i = j;
    }
  }
  res.second = getCostHP(i,s);
  return res;
}

{
  int i, j, k;
  pair<int,int> c1, c2;
  rd(N,K,(A--,B--,C)(N-1),Q);
  g.setEdge(N,N-1,A,B,C);
  hld.init(g.g);
  g.g.preorder(ord);

  rep[ord](i,N){
    j = hld.up(i);
    rep(k,18) up1[i][k] = up2[i][k] = -1;
    if(j==-1) continue;
    up1[i][0] = j;
    rep(k,g.es[i]) if(g.edge[i][k]==j) costHP[i][0] = g.cost[i][k], break;
    rep(k,1,18){
      up1[i][k] = up1[up1[i][k-1]][k-1];
      if(up1[i][k]==-1) break;
      costHP[i][k] = costHP[i][k-1] + costHP[up1[i][k-1]][k-1];
    }
  }

  rep[ord](i,N){
    dep[i] = k = hld.depth(i);
    j = bsearch_min[int,x,1,k+1](getCostHP(i,x) >= K);
    up2[i][0] = hld.up(i,j);
    rep(k,1,18){
      if(up2[i][k-1]==-1) break;
      up2[i][k] = up2[up2[i][k-1]][k-1];
    }
  }

  rep(Q){
    rd(S--,T--);
    k = hld.lca(S,T);
    c1 = getCost(S, dep[S]-dep[k]);
    c2 = getCost(T, dep[T]-dep[k]);
    wt(c1.first + c2.first + if[c1.second + c2.second >= K, 1, 0]);
  }
}

Current time: 2024年04月27日11時38分44秒
Last modified: 2019年12月27日20時36分54秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder
トップページに戻る

Logged in as: unknown user (not login)