yukicoder No.922 - 東北きりきざむたん

Source

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

問題概要

省略

解法

省略

cLay（version 20191108-1）のコード

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

int N, M, Q, A[1d5], B[1d5], X[1d5], Y[1d5];

int use[1d5], cnv_g[1d5], cnv_ind[1d5];
int gs, gn[1d5], gm[1d5], *ga[1d5], *gb[1d5];
int q1s[1d5], *q1v[1d5];
int q2s[1d5], *q2x[1d5], *q2y[1d5];

int cg;
graph g;
HLD hld;
int arr[1d5], dp[1d5];

void dfs(int n){
  dp[n] = arr[n];
  rep[g.edge[n]](i,g.es[n]) dfs(i), dp[n] += dp[i];
}

{
  int i, j, k, n;
  ll res = 0;
  unionFind uf;
  rd(N,M,Q,(A--,B--)(M),(X--,Y--)(Q));

  uf.malloc(N);
  uf.init(N);
  rep(i,N) uf(A[i], B[i]);
  rep(i,N) use[uf(i)] = 1;
  rep(i,1,N) use[i] += use[i-1];
  gs = use[N-1];
  rep(i,N) use[i]--;
  rep(i,N) cnv_g[i] = use[uf(i)];
  rep[cnv_g,i](k,N) cnv_ind[i] = gn[k]++;
  rep(i,M) gm[cnv_g[A[i]]]++, gm[cnv_g[B[i]]]++;
  rep(i,gs) walloc1d(&ga[i], gm[i]), walloc1d(&gb[i], gm[i]);
  rep(i,gs) gm[i] = 0;
  rep(i,M){
    k = cnv_g[A[i]];
    arrInsert(gm[k], gm[k], ga[k], cnv_ind[A[i]], gb[k], cnv_ind[B[i]]);
  }

  rep(i,Q){
    j = cnv_g[X[i]];
    k = cnv_g[Y[i]];
    if(j==k) q2s[j]++;
    if(j!=k) q1s[j]++, q1s[k]++;
  }
  rep(i,gs) walloc1d(&q1v[i], q1s[i]);
  rep(i,gs) walloc1d(&q2x[i], q2s[i]);
  rep(i,gs) walloc1d(&q2y[i], q2s[i]);
  rep(i,gs) q1s[i] = q2s[i] = q2s[i] = 0;
  rep(i,Q){
    j = cnv_g[X[i]];
    k = cnv_g[Y[i]];
    if(j==k) arrInsert(q2s[j], q2s[j], q2x[j], cnv_ind[X[i]], q2y[j], cnv_ind[Y[i]]);
    if(j!=k) arrInsert(q1s[j], q1s[j], q1v[j], cnv_ind[X[i]]);
    if(j!=k) arrInsert(q1s[k], q1s[k], q1v[k], cnv_ind[Y[i]]);
  }

  rep(cg,gs){
    g.setEdgeRootedTree(gn[cg], gm[cg], ga[cg], gb[cg]);
    hld.init(g);
    rep(i,q2s[cg]) res += hld.dist(q2x[cg][i], q2y[cg][i]);
    rep(i,gn[cg]) arr[i] = 0;
    rep(i,q1s[cg]) arr[q1v[cg][i]]++;
    dfs(0);
    n = 0;
    for(;;){
      rep[g.edge[n]](i,g.es[n]) if(2 * dp[i] > dp[0]) n = i, break_continue;
      break;
    }
    rep(i,q1s[cg]) res += hld.dist(n, q1v[cg][i]);
  }

  wt(res);
}

Current time: 2024年04月26日16時27分37秒
Last modified: 2019年11月10日18時37分14秒 (by laycrs)
Tags: Competitive_Programming_Incomplete yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン：