Educational Codeforces Round 73 G問題 - Graph And Numbers

Source

Educational Codeforces Round 73 G問題
Problem description

問題概要

省略

解法

省略

cLay（version 20190921-1）のコード

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

//no-unlocked
int N, M, A[1000], B[1000], ind[40];
ll dp[8], nx[8], now[8];
{
  int i, j, k;
  unionFind uf;
  graph og, g;
  
  rd(N,M,(A--,B--)(M));
  og.setEdge(N,M,A,B);

  uf.malloc(N);
  uf.init(N);
  rep(i,M) uf(A[i],B[i]);

  dp[0] = 1;
  rep(x,N){
    k = 0;
    rep(i,N){
      if(uf(i)!=x) ind[i] = -1;
      else         ind[i] = k++;
    }
    if(!k) continue;

    if(k==1){
      rep(i,8) now[i] = 0;
      now[0] = 2;
    } else {
      g = og.reduce(k, ind, 1, 1);
      now[0] = now[5] = 0;
      now[1] = now[4] = 1;
      now[2] = 2 * g.bipartite();
      now[3] = now[6] = g.countIndependenceSet() - 1 - now[2];
      now[7] = (1LL<<k) - sum(now(7));
    }
    
    rep(i,8) nx[i] = 0;
    rep(i,8) rep(j,8) nx[i|j] += dp[i] * now[j];
    rep(i,8) dp[i] = nx[i];
  }
  wt(dp[7]);
}

Current time: 2024年04月25日18時16分10秒
Last modified: 2019年09月21日12時34分33秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces
トップページに戻る

Logged in as: unknown user (not login)