Codeforces Round #684 DIV1 B問題/DIV2 D問題 - Graph Subset Problem

Source

Codeforces Round #684 DIV1 B問題 (1250pt)
Codeforces Round #684 DIV2 D問題 (2000pt)
Problem description

問題概要

省略

解法

省略

cLayversion 20201121-1)のコード

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

//no-unlocked
int N, M, K, A[1d5], B[1d5];
int deg[1d5], ok[1d5];
HashMap<int,int> hs[1d5];
graph g;
int ress, res[1d5];
{
  int i, j;
  LHeap<int> hp;
  hp.walloc(1d5);
  REP(rd_int()){
    rd(N,M,K,(A--,B--)(M));
    g.setEdge(N,M,A,B);
    rep(i,N) deg[i] = g.es[i];
    rep(i,N) hs[i].init(deg[i]);
    rep(i,M) hs[A[i]][B[i]] = hs[B[i]][A[i]] = 1;
    hp.init(N);
    rep(i,N) hp.change(i,deg[i]);
    rep(i,N) ok[i] = 1;

    while(hp.size){
      i = hp.pop();
      if(deg[i] >= K){
        ress = 0;
        rep(j,N) if(ok[j]) res[ress++] = j;
        wt(1, ress);
        wt(res(ress) + 1);
        break_continue;
      }
      if(deg[i] == K-1){
        ress = 0;
        res[ress++] = i;
        rep[g.edge[i]](j,g.es[i]) if(ok[j]) res[ress++] = j;
        rep(x,1,ress) rep(y,x+1,ress) if(!hs[res[x]].exist(res[y])) ress = 0, break_break;
        if(ress){
          wt(2);
          wt(res(ress) + 1);
          break_continue;
        }
      }
      ok[i] = 0;
      rep[g.edge[i]](j,g.es[i]) if(ok[j]){
        deg[j]--;
        hp.change(j,deg[j]);
      }
    }

    wt(-1);
  }
}

Current time: 2024年03月29日10時40分20秒
Last modified: 2020年11月21日18時56分47秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF684 CF_DIV1_B CF_DIV2_D
トップページに戻る

Logged in as: unknown user (not login)

ログイン: