QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#427070 | #5239. Mędrcy [A] | Bronya | 0 | 4ms | 4180kb | C++20 | 2.7kb | 2024-06-01 09:06:14 | 2024-06-01 09:06:14 |
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];
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==0)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;
if(now>ans||now>k)return;
}
if(now<=ans){
ans=now;
for(auto u:p)pd[u]--;
for(int i=1;i<=n;i++)pd[i]++;
}
}
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;
dfs(now+1);
chk[x]=false;
for(auto v:son[x])d[v]++;
for(auto v:th){
chk[v]=true;
for(auto y:son[v])d[y]--;
}
chk[x]=true;
dfs(now+d[x]);
chk[x]=false;
for(auto v:th){
chk[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: 3856kb
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:
4 8 1 2 3 4 5 7 8 9 1 2 4 6 2 3 1 2 3 2 3 1 2 3 4 6 2 4 5 6 7 8 3 5 2 3 4 5 7 0 4 1 2 3 4 4 8 1 2 3 4 5 6 8 9 4 8 1 2 3 4 5 6 8 9 -1 5 10 1 2 3 4 5 6 7 8 9 10 0 6 1 2 3 4 5 6 0 5 1 2 3 4 5 6 12 1 2 3 4 5 6 7 8 9 10 11 12 2 3 1 2 3 0 4 1 2 3 4 0 6 1 2 3 4 5 6 3 4 3 4 5 6 0 5 1 2 3 4 ...
result:
wrong answer 1st lines differ - expected: '6 6', found: '4 8'
Subtask #2:
score: 0
Wrong Answer
Test #13:
score: 0
Wrong Answer
time: 1ms
memory: 4160kb
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 8 1 2 3 4 6 7 9 11 4 8 1 2 3 4 5 6 7 8 1 11 1 2 3 4 5 6 7 8 9 10 11 -1 6 12 1 2 3 4 5 6 7 8 9 10 11 12 4 8 1 2 3 4 5 6 7 8 0 6 1 2 3 4 5 6 -1 1 1 10 2 3 1 2 3 2 4 5 6 9 10 0 9 1 2 3 4 5 6 7 8 9 0 5 1 2 3 4 5 0 6 1 2 3 4 5 6 0 4 1 2 3 4 5 7 1 2 5 6 8 9 11 2 3 1 2 3 0 5 1 2 3 4 5 0 5...
result:
wrong answer 2nd lines differ - expected: '1 3 4 5 7 8 9 10', found: '1 2 3 4 6 7 9 11 '
Subtask #3:
score: 0
Wrong Answer
Test #25:
score: 0
Wrong Answer
time: 1ms
memory: 4180kb
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:
10 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 7 13 1 2 3 4 5 6 7 8 9 10 11 13 14 0 13 1 2 3 4 5 6 7 8 9 10 11 12 13 5 10 1 2 3 4 5 6 7 8 9 10 8 17 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 2 14 1 2 3 4 5 6 7 8 9 10 11 12 13 14 8 17 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 0 14 1 2...
result:
wrong answer 1st lines differ - expected: '12 17', found: '10 20'
Subtask #4:
score: 0
Wrong Answer
Test #36:
score: 0
Wrong Answer
time: 1ms
memory: 3844kb
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:
0 11 1 2 3 4 5 6 7 8 9 10 11 0 10 1 2 3 4 5 6 7 8 9 10 5 9 1 2 3 4 5 6 7 9 10 9 18 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 6 12 1 2 3 4 5 7 8 9 10 11 12 13 6 11 1 2 3 4 5 6 7 9 10 11 12 6 12 1 2 3 4 5 6 7 8 9 10 11 12 0 10 1 2 3 4 5 6 7 8 9 10 5 9 1 2 4 5 6 7 8 9 10 7 14 1 2 3 4 5 6 7 ...
result:
wrong answer 1st lines differ - expected: '6 8', found: '0 11'
Subtask #5:
score: 0
Wrong Answer
Test #47:
score: 0
Wrong Answer
time: 1ms
memory: 3896kb
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:
8 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 7 14 1 2 3 4 5 6 7 8 9 10 11 12 13 15 5 8 1 2 4 5 6 7 8 11 5 10 1 2 3 4 5 6 7 8 9 10 8 17 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 7 14 1 2 3 5 6 7 8 9 10 11 12 13 14 16 8 17 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 8 17 1 2 3 4 5 6 8 9 10 11 12 1...
result:
wrong answer 1st lines differ - expected: '9 10', found: '8 16'
Subtask #6:
score: 0
Wrong Answer
Test #58:
score: 0
Wrong Answer
time: 4ms
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:
11 23 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 10 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 18 36 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 32 33 34 35 36 37 14 28 1 2 3 4 5 6 7 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25...
result:
wrong answer 1st lines differ - expected: '13 14', found: '11 23'
Subtask #7:
score: 0
Wrong Answer
Test #78:
score: 0
Wrong Answer
time: 0ms
memory: 3908kb
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:
10 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 14 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 12 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 19 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: '10 20'
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
Time Limit Exceeded
Test #121:
score: 0
Time Limit Exceeded
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...