QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#427096#5239. Mędrcy [A]Bronya0 5ms7720kbC++203.1kb2024-06-01 09:39:182024-06-01 09:39:19

Judging History

你现在查看的是最新测评结果

  • [2024-06-01 09:39:19]
  • 评测
  • 测评结果：0
  • 用时：5ms
  • 内存：7720kb
查看
  • [2024-06-01 09:39:18]
  • 提交

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;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

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'
English 繁體中文 简体中文

Server Time: 2024-12-05 05:59:11 | OpenSource Project