QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#455842 | #5239. Mędrcy [A] | JohnAlfnov | 0 | 11ms | 7944kb | C++14 | 1.9kb | 2024-06-26 21:29:26 | 2024-06-26 21:29:26 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int mp[1005][1005];
int vist[1005],deg[1005];
vector<int>g[1005];
int an,ans[1005];
int aa[1005],ac[1005];
int ab[1005],vv[1005],ba;
void dfss(int x){
ab[++ba]=x;vv[x]=1;
for(auto cu:g[x]){
if(vv[cu])continue;
dfss(cu);
}
}
void dfs(int z){
if(z<0)return;
int mx=-1,wz=0;
for(int i=1;i<=n;++i)if(!vist[i]){
if(mx<deg[i])mx=deg[i],wz=i;
}
if(mx<=2){
for(int i=1;i<=n;++i)vv[i]=vist[i],ac[i]=aa[i];
int he=0;
for(int i=1;i<=n;++i)if(!vv[i]&°[i]==1){
ba=0;dfss(i);
he+=ba/2;
if(ba%2)for(int j=2;j<=ba;j+=2)ac[ab[j]]=1;
else for(int j=1;j<=ba;++j)ac[ab[j]]=1;
}
for(int i=1;i<=n;++i)if(!vv[i]&°[i]==2){
ba=0;dfss(i);
he+=(ba+1)/2;
for(int j=1;j<=ba;++j)ac[ab[j]]=1;
}
if(z<he)return;
int na=k-(z-he);
if(an>na){
an=na;
for(int i=1;i<=n;++i)ans[i]=0;
}
if(an==na){
for(int i=1;i<=n;++i)ans[i]|=ac[i];
}
return;
}
vist[wz]=1;aa[wz]=1;
for(auto cu:g[wz])if(!vist[cu])--deg[cu];
dfs(z-1);
vist[wz]=0;aa[wz]=0;
for(auto cu:g[wz])if(!vist[cu])++deg[cu];
vist[wz]=1;
int gs=0;
for(auto cu:g[wz])if(!vist[cu]){
++gs;
vist[cu]=1;aa[cu]=1;--deg[cu];
}
dfs(z-gs);
vist[wz]=0;
for(auto cu:g[wz])if(!vist[cu]){
vist[cu]=0;aa[cu]=0;++deg[cu];
}
}
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;++i)vist[i]=0,deg[i]=0,aa[i]=0,g[i].clear();
for(int i=1;i<n;++i)for(int j=i+1;j<=n;++j)mp[i][j]=0;
for(int i=1;i<=m;++i){
int a,b;
scanf("%d%d",&a,&b);
if(mp[a][b])continue;
mp[a][b]=1;
++deg[a],++deg[b];
g[a].emplace_back(b);
g[b].emplace_back(a);
}
an=k+1;
dfs(k);
if(an>k)puts("-1");
else{
int he=0;
for(int i=1;i<=n;++i)he+=ans[i];
printf("%d %d\n",an,he);
for(int i=1;i<=n;++i)if(ans[i])printf("%d ",i);
printf("\n");
}
}
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3912kb
input:
136 9 37 11 2 7 2 5 2 5 6 8 2 4 2 9 4 5 6 8 6 7 3 9 3 6 3 8 1 9 2 9 4 6 2 4 1 4 7 9 7 9 4 7 3 6 4 5 2 7 1 5 6 9 4 9 4 5 2 7 3 9 1 9 2 7 5 7 1 2 2 3 1 8 3 8 1 3 7 1 13 4 6 3 36 2 2 3 2 3 1 2 2 3 1 3 1 3 1 3 1 2 1 2 1 2 1 2 1 2 1 3 1 2 1 3 1 3 1 2 1 3 1 2 1 3 1 2 2 3 1 2 1 3 1 3 2 3 1 3 2 3 2 3 1 2 1 ...
output:
1 8 1 2 3 4 5 7 8 9 1 2 4 6 2 3 1 2 3 2 3 1 2 3 1 6 1 2 3 5 8 9 1 5 1 4 5 6 7 3 4 1 2 3 4 0 7 2 3 5 6 7 8 9 1 6 3 4 5 6 7 9 -1 1 9 1 2 3 4 5 6 8 9 10 1 5 2 3 4 5 6 1 4 2 3 4 5 3 9 1 2 5 6 8 9 10 11 12 2 3 1 2 3 2 2 2 4 1 5 1 2 4 5 6 3 3 1 3 4 1 4 2 3 4 5 4 5 1 2 3 6 10 2 3 1 2 3 ...
result:
wrong answer 1st lines differ - expected: '6 6', found: '1 8'
Subtask #2:
score: 0
Wrong Answer
Test #13:
score: 0
Wrong Answer
time: 1ms
memory: 4000kb
input:
139 11 16 6 3 4 1 3 5 7 3 6 3 9 7 10 3 8 1 2 4 8 1 11 4 8 4 9 3 6 4 9 5 9 1 6 8 23 11 2 4 4 8 3 6 4 5 1 3 5 7 3 8 2 5 1 6 1 5 5 8 6 7 1 3 3 5 6 7 7 8 6 8 5 8 4 6 4 8 2 3 1 5 2 8 11 31 1 5 11 3 11 5 7 1 9 3 5 3 5 1 2 1 5 5 7 9 10 2 6 2 7 2 9 5 9 1 11 5 8 4 8 5 6 4 10 3 10 2 9 7 11 5 9 2 6 8 9 9 10 8 ...
output:
5 11 1 2 3 4 5 6 7 8 9 10 11 0 6 1 2 3 4 7 8 -1 -1 0 10 1 3 4 5 6 7 8 10 11 12 1 6 2 4 5 6 7 8 1 5 1 3 4 5 6 -1 1 1 10 2 3 1 2 3 2 4 5 6 9 10 1 7 1 2 4 5 6 7 8 1 4 2 3 4 5 1 5 2 3 4 5 6 3 4 1 2 3 4 2 10 1 2 3 4 6 7 8 9 10 11 2 3 1 2 3 1 4 2 3 4 5 1 4 1 3 4 5 2 3 1 2 3 -1 2 4 1 2 3 7...
result:
wrong answer 1st lines differ - expected: '5 8', found: '5 11'
Subtask #3:
score: 0
Wrong Answer
Test #25:
score: 0
Wrong Answer
time: 1ms
memory: 3936kb
input:
66 20 51 30 2 4 5 8 19 20 10 11 7 12 1 20 5 13 12 14 13 15 11 14 4 5 9 16 14 15 5 9 6 14 5 6 3 16 9 18 6 8 14 19 7 8 12 15 8 17 11 14 4 9 11 20 2 13 3 18 5 20 11 13 13 18 3 17 15 20 8 13 4 10 1 6 3 5 7 8 12 14 2 20 4 15 3 20 8 9 3 20 2 16 3 10 2 7 5 19 3 8 8 20 7 10 15 58 30 7 15 8 13 3 13 3 8 4 8 1...
output:
1 18 1 2 3 4 6 7 8 9 10 11 12 13 15 16 17 18 19 20 0 13 1 2 3 5 6 7 8 10 11 12 13 14 15 0 11 1 2 3 4 5 6 7 9 10 12 13 1 9 1 2 3 4 5 6 7 9 11 2 16 1 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 0 12 2 3 4 6 7 8 9 10 11 12 13 14 1 14 2 3 4 6 7 8 9 10 11 12 14 15 16 17 1 12 1 2 3 4 6 7 8 10 11 12 13 14 ...
result:
wrong answer 1st lines differ - expected: '12 17', found: '1 18'
Subtask #4:
score: 0
Wrong Answer
Test #36:
score: 0
Wrong Answer
time: 1ms
memory: 5976kb
input:
67 11 28 30 1 7 1 5 4 11 1 2 2 10 9 11 8 9 7 9 4 8 4 9 5 8 5 7 5 8 2 11 8 10 1 3 2 11 5 8 2 4 7 10 8 11 6 11 2 4 2 11 1 6 10 11 8 11 3 8 10 44 30 5 8 1 4 1 4 3 9 1 4 6 7 3 8 6 7 4 8 4 6 1 2 4 7 1 8 1 5 9 10 2 10 7 8 2 8 1 9 1 5 5 10 1 7 4 6 7 10 2 5 4 8 6 8 8 9 7 10 6 10 4 10 3 5 2 9 6 10 4 8 5 10 5...
output:
1 9 2 3 4 5 6 7 9 10 11 1 7 2 4 5 6 7 8 9 1 10 1 2 3 4 5 6 7 8 10 11 5 14 1 3 4 5 6 7 8 9 10 11 13 14 15 17 2 12 1 2 3 4 5 6 7 9 10 11 12 13 2 10 1 2 3 4 5 7 10 11 12 13 2 10 1 2 3 5 6 7 8 9 10 12 1 9 1 2 3 4 5 6 7 8 10 3 11 1 2 3 4 5 6 7 8 9 10 11 2 12 2 3 4 5 6 7 8 9 10 12 13 14 2 8 1 3 ...
result:
wrong answer 1st lines differ - expected: '6 8', found: '1 9'
Subtask #5:
score: 0
Wrong Answer
Test #47:
score: 0
Wrong Answer
time: 1ms
memory: 4076kb
input:
64 16 32 30 8 13 8 11 5 12 3 10 3 8 6 15 12 13 5 7 1 2 8 14 2 4 8 16 14 15 3 13 6 9 1 11 4 8 15 16 9 12 10 16 4 8 4 5 3 6 3 15 6 14 5 11 3 11 1 15 4 15 6 13 8 14 7 13 15 42 30 1 4 5 13 12 13 9 12 4 9 10 11 9 11 5 6 2 6 3 11 5 14 8 11 4 7 1 15 6 14 2 14 4 11 1 5 6 8 1 7 1 5 9 14 7 15 7 8 5 7 3 9 12 1...
output:
2 12 1 2 3 4 6 7 9 11 12 13 14 16 3 12 1 2 3 4 5 8 10 11 12 13 14 15 1 9 1 2 4 5 6 7 8 9 10 0 9 2 3 4 5 6 7 8 9 11 1 15 1 2 4 6 7 8 9 10 11 12 13 14 15 16 17 2 8 3 5 8 9 10 12 14 16 0 12 2 5 6 7 9 10 11 13 14 15 16 17 4 13 1 2 3 5 6 8 10 11 12 13 14 17 18 4 13 2 3 4 6 7 8 10 11 12 13 14 15 1...
result:
wrong answer 1st lines differ - expected: '9 10', found: '2 12'
Subtask #6:
score: 0
Wrong Answer
Test #58:
score: 0
Wrong Answer
time: 3ms
memory: 3980kb
input:
32 23 77 30 4 18 1 20 11 20 6 22 7 18 2 17 10 14 3 6 15 22 3 13 14 17 4 16 14 23 1 10 9 14 6 20 4 9 11 16 20 22 5 13 3 23 8 20 2 16 12 16 5 20 1 19 3 8 9 17 15 21 18 23 1 6 3 16 2 6 16 22 16 22 6 15 14 21 4 22 12 19 10 21 2 18 1 10 15 22 7 20 6 19 13 22 5 16 7 22 21 23 14 15 5 16 11 20 10 16 18 19 5...
output:
0 18 1 2 3 4 5 7 8 10 11 12 13 14 15 17 19 20 22 23 2 19 1 2 3 4 5 6 7 8 9 10 12 13 14 15 17 18 19 20 21 2 34 2 3 4 5 6 7 8 9 10 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 35 36 37 1 25 1 2 3 4 5 7 9 10 11 12 13 14 15 16 17 18 19 22 23 24 25 26 27 28 29 1 27 2 4 5 6 8 9 11...
result:
wrong answer 1st lines differ - expected: '13 14', found: '0 18'
Subtask #7:
score: 0
Wrong Answer
Test #78:
score: 0
Wrong Answer
time: 2ms
memory: 4068kb
input:
36 20 64 30 5 6 7 14 14 18 13 17 15 16 15 18 2 13 6 20 3 8 10 16 10 20 12 14 15 17 3 4 3 11 6 12 8 11 11 14 8 16 12 20 3 4 18 20 9 12 16 20 11 17 4 7 2 9 12 18 18 20 3 15 12 17 1 7 3 11 1 16 12 20 1 6 8 20 10 19 10 15 14 18 14 18 3 16 3 7 12 19 2 17 4 11 12 20 1 12 5 8 10 17 18 19 12 19 3 17 11 19 3...
output:
2 17 1 4 5 6 7 8 9 10 11 13 14 15 16 17 18 19 20 1 21 1 2 3 4 6 7 10 14 15 16 17 19 20 21 22 24 25 26 27 28 29 1 20 1 2 3 4 6 7 8 9 10 11 12 13 14 15 17 18 19 20 21 24 5 30 1 2 3 4 5 7 12 13 15 16 17 18 19 20 21 22 23 24 25 28 29 30 31 32 33 34 35 36 37 38 2 24 3 4 5 6 8 9 10 14 15 16 19 20 21 2...
result:
wrong answer 1st lines differ - expected: '12 15', found: '2 17'
Subtask #8:
score: 0
Time Limit Exceeded
Test #97:
score: 0
Time Limit Exceeded
input:
1 1000 3000 30 82 508 127 347 370 658 350 586 486 863 28 99 293 422 427 710 731 936 555 856 91 374 133 676 351 806 780 992 132 686 73 813 212 971 161 919 402 666 59 106 682 766 288 570 199 882 332 428 633 693 306 694 319 882 356 582 546 916 305 665 336 534 608 901 222 228 422 860 406 869 457 524 114...
output:
result:
Subtask #9:
score: 0
Time Limit Exceeded
Test #109:
score: 0
Time Limit Exceeded
input:
1 1000 3000 30 126 407 55 812 361 478 617 796 500 641 338 450 587 739 1 159 753 795 521 995 313 981 35 595 364 914 334 672 615 802 466 789 262 852 258 867 475 686 543 902 334 795 470 899 146 823 713 850 305 574 201 332 119 298 387 747 187 999 95 981 349 731 749 883 829 895 380 818 568 856 738 981 69...
output:
result:
Subtask #10:
score: 0
Wrong Answer
Test #121:
score: 0
Wrong Answer
time: 11ms
memory: 7944kb
input:
1 1000 3000 30 530 695 780 873 245 704 66 567 435 786 5 536 743 895 374 505 283 773 10 50 250 840 100 416 321 704 390 1000 786 921 374 549 490 626 362 759 661 929 589 704 390 446 123 725 371 447 380 930 10 106 661 876 615 695 410 695 421 695 390 561 10 209 338 780 18 345 41 123 121 773 345 384 558 9...
output:
6 931 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 43 44 45 46 47 48 49 50 51 52 53 54 56 57 58 59 60 61 62 63 64 65 66 67 68 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 88 89 90 92 93 94 95 96 97 98 99 100 101 102 103 104 105 ...
result:
wrong answer 1st lines differ - expected: '29 29', found: '6 931'