Codeforces Round #600 DIV2 F問題 - Cheap Robot

Source

Codeforces Round #600 DIV2 F問題 (2750pt)
Problem description

問題概要

省略

解法

省略

cLayversion 20191125-1)のコード

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

//no-unlocked
int N, M, K, Q, A[3d5], B[3d5], X, Y; ll C[3d5];

int ss[1d5];
int mmm, aaa[3d5], bbb[3d5]; ll ccc[3d5];
int mm, aa[1d5], bb[1d5]; ll cc[1d5];
ll arr[1d5];

{
  int i, j, k;
  wgraph<ll> g;
  unionFind uf;
  HLD hld;
  HLD_segtree<ll> t;
  LHeap<ll> hp;
  ll tmp;

  rd(N,M,K,Q,(A--,B--,C)(M));
  g.setEdge(N,M,A,B,C);

  hp.malloc(N);
  hp.init(N);
  rep(i,K) hp.change(i,0);
  rep(i,K,N) hp.change(i,ll_inf);
  rep(i,K) ss[i] = i;
  while(hp.size){
    i = hp.pop();
    rep(j,g.es[i]){
      k = g.edge[i][j];
      if(hp.val[k] > hp.val[i] + g.cost[i][j]){
        hp.change(k, hp.val[i] + g.cost[i][j]);
        ss[k] = ss[i];
      }
    }
  }

  uf.malloc(N);
  uf.init(N);
  rep(i,M) if(ss[A[i]] != ss[B[i]]) arrInsert(mmm, mmm, aaa, ss[A[i]], bbb, ss[B[i]], ccc, hp.val[A[i]] + hp.val[B[i]] + C[i]);
  sortA(mmm,ccc,aaa,bbb);
  rep(i,mmm) if(uf(aaa[i],bbb[i])) arrInsert(mm, mm, aa, aaa[i], bb, bbb[i], cc, ccc[i]);

  g.setEdge(K, mm, aa, bb, cc);
  hld.init(g.g);

  rep(i,mm){
    j = hld.depth(aa[i]);
    k = hld.depth(bb[i]);
    if(j > k) arr[aa[i]] = -cc[i];
    else      arr[bb[i]] = -cc[i];
  }

  t.init(&hld, arr);
  rep(Q){
    rd(X--,Y--);
    k = hld.lca(X, Y);
    t.change(k,k,1);
    wt(-t.getMinVal(X,Y));
    t.change(k,k,arr[k]);
  }
}

Current time: 2021年09月27日22時08分32秒
Last modified: 2019年11月25日23時07分17秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF600 CF_Div2_F
トップページに戻る

Logged in as: unknown user (not login)

ログイン: