Codeforces Round #684 DIV1 B問題 (1250pt)
Codeforces Round #684 DIV2 D問題 (2000pt)
Problem description
省略
省略
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)