QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#427096 | #5239. Mędrcy [A] | Bronya | 0 | 5ms | 7720kb | C++20 | 3.1kb | 2024-06-01 09:39:18 | 2024-06-01 09:39:19 |
answer
#include<bits/stdc++.h>
using namespace std;
int T;
int n,m,k,ans;
int pd[1005];
int G[1005][1005],d[1005];
bool chk[1005],vis[1005],hav[1005];
vector<int>son[1005];
vector<int>sav;
void dfs2(int u){
vis[u]=true;sav.push_back(u);
for(auto v:son[u])
if(!vis[v])dfs2(v);
}
void dfs(int now){
if(now>ans||now>k)return;
int x=0;
for(int i=1;i<=n;i++){
if(chk[i])continue;
if(d[i]>d[x])x=i;
}
if(d[x]<=2){
for(int i=1;i<=n;i++)vis[i]=false;
vector<int>p;
for(int i=1;i<=n;i++)
if(!vis[i]&&!chk[i]&&d[i]<=1){
sav.clear();
dfs2(i);
now+=sav.size()/2;
if(sav.size()%2==1)
for(int j=0;j<sav.size();j++){
if(j%2==1)p.push_back(sav[j]);
}
else for(int j=0;j<sav.size();j++)p.push_back(sav[j]);
if(now>ans||now>k)return;
}
for(int i=1;i<=n;i++)
if(!vis[i]&&!chk[i]&&d[i]<=2){
sav.clear();
dfs2(i);
now+=(sav.size()+1)/2;
for(int j=0;j<sav.size();j++)p.push_back(sav[j]);
if(now>ans||now>k)return;
}
if(now<=ans){
if(now<ans)
for(int i=1;i<=n;i++)pd[i]=false;
ans=now;
for(int i=1;i<=n;i++)
if(hav[i])pd[i]=true;
for(auto u:p)pd[u]=true;
}
return ;
}
else {
vector<int>th;
for(auto v:son[x])
if(!chk[v])th.push_back(v);
for(auto v:son[x])d[v]--;
chk[x]=true;hav[x]=true;
dfs(now+1);
chk[x]=false;hav[x]=false;
for(auto v:son[x])d[v]++;
int sd=d[x];
for(auto v:th){
chk[v]=true;hav[v]=true;
for(auto y:son[v])d[y]--;
}
chk[x]=true;
dfs(now+sd);
chk[x]=false;
for(auto v:th){
chk[v]=false;hav[v]=false;
for(auto y:son[v])d[y]++;
}
}
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++){
pd[i]=false;son[i].clear();
for(int j=1;j<=n;j++)
G[i][j]=0;
}
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
G[u][v]=G[v][u]=1;
}
for(int i=1;i<=n;i++){
d[i]=0;
for(int j=1;j<=n;j++)
if(G[i][j]){
d[i]++;
son[i].push_back(j);
}
}
ans=k+1;
dfs(0);
if(ans==k+1)puts("-1");
else {
vector<int>lans;
for(int i=1;i<=n;i++)
if(pd[i])lans.push_back(i);
printf("%d %d\n",ans,(int)lans.size());
for(int i=1;i<=n;i++)
if(pd[i])printf("%d ",i);
putchar('\n');
}
}
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 4180kb
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:
8 6 1 2 3 4 6 9 1 2 4 6 2 3 1 2 3 2 3 1 2 3 7 4 2 4 6 7 6 5 1 2 3 4 5 3 4 1 2 3 4 8 5 1 4 5 6 8 7 7 1 2 4 5 6 8 9 -1 -1 5 6 1 2 3 4 5 6 4 5 1 2 3 4 5 9 12 1 2 3 4 5 6 7 8 9 10 11 12 2 3 1 2 3 3 4 1 2 3 4 -1 4 3 3 4 5 4 5 1 2 3 4 5 5 4 2 3 5 10 2 3 1 2 3 5 6 1 2 3 4 5 6 7 6 1 2 5 6...
result:
wrong answer 1st lines differ - expected: '6 6', found: '8 6'
Subtask #2:
score: 0
Wrong Answer
Test #13:
score: 0
Wrong Answer
time: 1ms
memory: 3888kb
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:
-1 7 8 1 2 3 4 5 6 7 8 -1 -1 11 12 1 2 3 4 5 6 7 8 9 10 11 12 8 5 1 3 4 6 8 5 6 1 2 3 4 5 6 -1 1 1 10 2 3 1 2 3 2 4 5 6 9 10 -1 4 5 1 2 3 4 5 5 6 1 2 3 4 5 6 3 4 1 2 3 4 9 6 1 2 5 7 8 11 2 3 1 2 3 4 5 1 2 3 4 5 4 5 1 2 3 4 5 2 3 1 2 3 -1 2 4 1 2 3 7 -1 6 5 2 5 6 7 9 3 4 1 2 3 4 3 2...
result:
wrong answer 1st lines differ - expected: '5 8', found: '-1'
Subtask #3:
score: 0
Wrong Answer
Test #25:
score: 0
Wrong Answer
time: 1ms
memory: 3912kb
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:
18 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 14 12 2 3 4 5 6 8 9 10 11 12 13 15 11 11 1 2 3 4 5 6 7 9 10 12 13 11 7 1 4 5 6 8 10 11 16 13 1 2 3 5 6 7 8 9 10 12 14 16 17 12 12 1 2 3 4 5 6 7 8 9 11 13 14 15 11 1 3 4 5 6 7 8 10 11 13 15 12 12 1 2 3 4 6 7 8 10 11 12 13 14 9 12 1 2 3 ...
result:
wrong answer 1st lines differ - expected: '12 17', found: '18 20'
Subtask #4:
score: 0
Wrong Answer
Test #36:
score: 0
Wrong Answer
time: 1ms
memory: 3916kb
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:
9 11 1 2 3 4 5 6 7 8 9 10 11 9 10 1 2 3 4 5 6 7 8 9 10 11 7 2 3 5 6 9 10 11 14 18 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 12 7 2 3 4 8 10 11 13 11 8 2 5 6 7 8 9 11 12 10 12 1 2 3 4 5 6 7 8 9 10 11 12 9 10 1 2 3 4 5 6 7 8 9 10 9 8 1 3 4 5 7 8 9 10 12 14 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ...
result:
wrong answer 1st lines differ - expected: '6 8', found: '9 11'
Subtask #5:
score: 0
Wrong Answer
Test #47:
score: 0
Wrong Answer
time: 1ms
memory: 3920kb
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:
13 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 13 11 1 3 4 5 6 7 8 9 11 13 15 11 8 1 3 4 5 6 7 8 11 11 8 1 2 3 4 6 7 9 10 16 12 3 4 5 6 7 8 9 10 12 13 15 16 11 14 1 2 3 5 6 7 8 9 10 11 12 13 14 16 17 17 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 12 10 1 4 5 6 9 12 13 14 15 18 11 14 1 2 3 4 6 7 ...
result:
wrong answer 1st lines differ - expected: '9 10', found: '13 16'
Subtask #6:
score: 0
Wrong Answer
Test #58:
score: 0
Wrong Answer
time: 5ms
memory: 3964kb
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:
22 18 2 3 4 6 7 8 9 10 11 13 14 16 18 19 20 21 22 23 20 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 -1 28 19 1 3 4 5 6 7 10 11 13 14 15 17 19 20 21 22 24 27 29 29 32 1 2 3 4 5 6 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 -1 17 20 1 2 3 4 5 6 7 8 9 10 11...
result:
wrong answer 1st lines differ - expected: '13 14', found: '22 18'
Subtask #7:
score: 0
Wrong Answer
Test #78:
score: 0
Wrong Answer
time: 4ms
memory: 4024kb
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:
19 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 25 28 1 2 3 4 5 6 7 8 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 25 24 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 30 38 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31...
result:
wrong answer 1st lines differ - expected: '12 15', found: '19 20'
Subtask #8:
score: 0
Wrong Answer
Test #97:
score: 1
Accepted
time: 3ms
memory: 7648kb
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:
-1
result:
ok single line: '-1'
Test #98:
score: 0
Wrong Answer
time: 0ms
memory: 7696kb
input:
1 1000 3000 30 266 447 201 576 363 986 110 318 382 520 182 339 5 235 676 781 736 919 396 814 265 779 677 862 67 354 154 603 440 751 642 911 422 642 23 154 110 861 167 400 316 619 778 789 461 668 621 677 339 419 154 248 354 550 398 701 73 940 461 829 547 923 643 986 339 985 110 901 96 461 560 856 552...
output:
-1
result:
wrong answer 1st lines differ - expected: '30 30', found: '-1'
Subtask #9:
score: 0
Wrong Answer
Test #109:
score: 1
Accepted
time: 0ms
memory: 7676kb
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:
-1
result:
ok single line: '-1'
Test #110:
score: 0
Wrong Answer
time: 4ms
memory: 7720kb
input:
1 1000 3000 30 534 661 174 197 306 990 51 215 197 622 327 560 503 769 462 503 88 327 150 713 77 876 441 755 150 354 14 974 35 281 441 537 501 766 621 657 309 568 234 854 278 657 115 503 162 501 976 990 121 618 441 814 439 854 447 876 197 509 604 925 632 849 281 382 15 319 211 854 258 281 56 501 296 ...
output:
-1
result:
wrong answer 1st lines differ - expected: '30 30', found: '-1'
Subtask #10:
score: 0
Wrong Answer
Test #121:
score: 0
Wrong Answer
time: 0ms
memory: 7660kb
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:
-1
result:
wrong answer 1st lines differ - expected: '29 29', found: '-1'