Codeforces Round #589 DIV2 F問題 - One Node is Gone

Source

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

問題概要

省略

解法

省略

cLay（version 20191006-1）のコード

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

//no-unlocked
int D, N, A[140000], B[140000];
int cnt[5];
int ress, res[10];
graph g;

int solve(int n, int b, int sp, int rm){
  int i, j, lis[3], s = 0, x, y;

  if(rm < 0) return 0;

  rep(i,g.es[n]){
    j = g.edge[n][i];
    if(j != b) lis[s++] = j;
  }

  if(s==0 && rm==0 && sp!=n) return 1;
  if(s==0) return 0;

  if(s==1 && sp==n) return solve(lis[0], n, sp, rm-1);
  if(s==1) return 0;

  if(s==2 && sp!=n){
    rep(i,2) if(!solve(lis[i], n, sp, rm-1)) return 0;
    return 1;
  }
  if(s==2) return 0;

  if(s==3 && sp==n){
    x = 1;
    y = 2;
    rep(i,3){
      if(x && solve(lis[i], n, sp, rm-1)) x--, continue;
      if(y && solve(lis[i], n, sp, rm-2)) y--, continue;
      return 0;
    }
    return 1;
  }

  return 0;
}

{
  rd(D);
  N = (1<<D) - 2;
  rd((A--,B--)(N-1));
  g.setEdge(N,N-1,A,B);
  rep(i,N) if(g.es[i] > 4) wt(0), return 0;
  rep(i,N) cnt[g.es[i]]++;

  if(D==2){
    res[ress++] = 0;
    res[ress++] = 1;
    wt(ress);
    wt(res(ress)+1);
    return 0;
  }

  if(cnt[4]==1 && cnt[2]==1){
    rep(i,N) if(g.es[i] == 4) break;
    rep(k,N) if(g.es[k] == 2) break;
    if(solve(k,-1,i,D-1)) res[ress++] = i;
  } else if(cnt[2] == 2) {
    rep(i,N) if(g.es[i] == 2) break;
    rep(j,i+1,N) if(g.es[j] == 2) break;
    if(solve(i,-1,j,D-1)) res[ress++] = j;
    if(solve(j,-1,i,D-1)) res[ress++] = i;
  } else {
    rep(i,N) if(g.es[i]==3 && solve(i,-1,i,D-1)) res[ress++] = i;
  }

  sortA(ress, res);
  wt(ress);
  wt(res(ress)+1);
}

Current time: 2024年04月26日21時10分26秒
Last modified: 2019年10月06日04時51分17秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF589 CF_Div2_F
トップページに戻る

Logged in as: unknown user (not login)