QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#654099#4829. Mark on a Graphrotcar070 2ms4616kbC++23798b2024-10-18 21:05:132024-10-18 21:05:44

Judging History

This is the latest submission verdict.

  • [2024-10-18 21:05:44]
  • Judged
  • Verdict: 0
  • Time: 2ms
  • Memory: 4616kb
  • [2024-10-18 21:05:13]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
constexpr int N=1005;
int n,m,deg[N];bool g[N][N];
int main(){
    cin>>n>>m;int up=(n-1)/m+1;
    for(int i=1,u,v;i<=m;i++) cin>>u>>v,g[v][u]=g[u][v]=1,deg[u]++,deg[v]++;
    bool win=0;
    for(int i=1;i<=n&&!win;i++)if(deg[i]<=up+5){
        int cnt=0;
        for(int j=1;j<=n;j++) if(g[i][j]&&deg[j]<=up+1) cnt++;
        if(cnt>=5) win=1;
    }
    if(win) return puts("ok"),0;
    puts("mark");
    for(int i=1;i<=n;i++)if(deg[i]<=up){
        int cnt=5;
        vector<pair<int,int>> v;
        for(int j=i+1;j<=n&&cnt;j++) if(deg[j]<=up){
            cnt--;
            if(!g[i][j]) v.emplace_back(i,j);
        }
        cout<<v.size()<<'\n';
        for(auto [x,y]:v) cout<<x<<' '<<y<<'\n';
        return 0;
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 4616kb

input:

1000 3560
603 151
415 20
102 569
895 552
678 734
24 614
689 518
440 223
751 919
223 433
711 551
502 634
706 583
812 501
514 535
780 751
720 530
532 384
888 139
864 791
292 675
171 881
30 592
464 557
280 299
654 650
894 335
250 532
792 10
83 969
118 771
579 300
852 983
243 940
957 939
817 889
911 319...

output:

mark
5
501 655
501 691
501 762
501 862
501 880

input:

1000 3565
626 643
295 222
665 298
534 33
682 275
706 833
155 262
656 841
184 286
383 844
86 259
937 771
37 355
379 167
640 763
707 250
693 401
224 873
974 302
521 380
368 663
676 977
113 210
175 831
554 526
553 125
506 102
70 757
464 840
87 733
956 373
600 53
178 201
182 394
201 34
975 583
557 937
2...

output:

ok

result:

ok all right

Test #2:

score: 100
Accepted
time: 1ms
memory: 4612kb

input:

1000 2000
457 335
160 497
464 992
892 255
853 3
308 301
970 363
541 299
89 418
425 128
626 827
603 854
484 874
755 295
607 483
798 552
356 850
320 357
254 940
675 901
168 525
301 636
520 555
773 910
343 701
889 966
218 529
909 950
71 64
682 284
424 138
721 792
670 544
386 72
654 909
725 235
592 437
...

output:

mark
5
6 18
6 22
6 53
6 66
6 67

input:

1000 2005
674 235
170 611
339 156
250 778
470 422
361 300
610 274
440 112
90 337
81 879
505 764
37 6
935 217
424 667
914 38
740 19
121 843
87 330
441 646
764 431
882 331
763 804
318 988
904 500
999 663
53 985
978 756
246 228
131 622
58 21
528 824
411 674
835 561
569 980
502 456
164 502
633 94
303 24...

output:

ok

result:

ok all right

Test #3:

score: 0
Wrong Answer on the first run

input:

1000 5000
449 632
597 26
701 322
249 190
411 770
666 596
989 995
112 861
445 818
544 659
24 680
739 593
344 439
193 932
600 526
574 869
216 918
716 793
259 686
555 993
255 578
659 271
328 524
729 672
39 771
241 866
27 790
417 109
56 403
338 299
387 232
280 306
589 794
833 419
900 802
54 697
539 807
...

output:

mark

input:


output:


result:

wrong output format Unexpected end of file - int32 expected