QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #277128 | #7514. Clique Challenge | ship2077 | AC ✓ | 204ms | 47408kb | C++14 | 1.2kb | 2023-12-06 15:32:59 | 2023-12-06 15:33:00 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
constexpr int N=22,M=1e3+5,mod=1e9+7;
bool vis[M][M];long long g[1<<N],edge[50];
int n,m,x,y,ans,lim,deg[M],q[50],f[1<<N];
int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
return x*f;
}
int reduce(int x){return x>=mod?x-mod:x;}
int main(){
n=read();m=read();
for (int i=1;i<=m;i++){
x=read();y=read();
deg[x]++;deg[y]++;
vis[x][y]=vis[y][x]=1;
}
for (int i=1;i<=n;i++){m=0;
for (int j=1;j<=n;j++)
if (vis[i][j]&&(deg[j]>deg[i]||deg[i]==deg[j]&&j>=i))
q[m++]=j;
lim=(1<<(m>>1))-1; f[0]=1;
for (int i=0;i<m;i++) edge[i]=0;
for (int i=0;i<m;i++)
for (int j=0;j<m;j++)
if (i^j&&!vis[q[i]][q[j]])
edge[i]|=1ll<<j;
for (int s=1;s<=lim;s++){
const int x=s&-s;
g[s]=g[s^x]|edge[__lg(x)];
f[s]=!(s&g[s]);
}
for (int i=1;i<=lim;i<<=1)
for (int j=0;j<=lim;j++)
if (i&j) f[j]+=f[j^i];
ans=reduce(ans+f[lim]);
for (int s=1;s<(1<<(m+1>>1));s++){
const int x=s&-s;
g[s]=g[s^x]|edge[__lg(x)+(m>>1)];
if (!(g[s]>>(m>>1)&s)) ans=reduce(ans+f[lim^(lim&g[s])]);
}
}
printf("%d\n",ans);
return 0;
}
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7884kb
input:
3 2 1 2 2 3
output:
5
result:
ok single line: '5'
Test #2:
score: 0
Accepted
time: 1ms
memory: 7848kb
input:
3 3 1 2 1 3 2 3
output:
7
result:
ok single line: '7'
Test #3:
score: 0
Accepted
time: 1ms
memory: 7876kb
input:
1000 100 446 789 167 547 254 777 777 185 33 446 777 847 185 877 757 167 72 383 847 446 254 478 959 185 757 446 847 959 959 167 757 847 747 757 446 167 989 757 547 777 33 747 33 254 254 843 33 547 446 980 877 205 185 72 980 959 33 205 877 757 33 847 478 843 757 478 167 877 72 789 877 959 980 478 167 ...
output:
1373
result:
ok single line: '1373'
Test #4:
score: 0
Accepted
time: 14ms
memory: 12328kb
input:
1000 1000 770 105 219 498 686 498 343 534 15 591 919 588 149 588 298 915 551 523 710 116 105 637 523 991 343 476 145 420 604 588 254 120 551 421 476 298 900 710 915 343 445 421 986 867 445 588 219 356 919 105 584 875 991 604 776 919 588 254 919 421 356 348 105 551 15 113 919 15 356 523 343 155 770 9...
output:
6621319
result:
ok single line: '6621319'
Test #5:
score: 0
Accepted
time: 25ms
memory: 12320kb
input:
1000 1000 840 251 559 572 77 993 857 254 176 77 30 423 838 251 862 466 920 254 254 593 593 423 780 575 487 865 952 176 480 77 351 487 620 390 231 496 423 761 993 385 383 390 220 620 862 805 920 838 77 339 838 231 691 384 930 251 840 77 593 993 838 930 176 761 383 761 480 487 251 383 295 390 289 808 ...
output:
6403686
result:
ok single line: '6403686'
Test #6:
score: 0
Accepted
time: 23ms
memory: 8556kb
input:
1000 1000 179 73 322 80 586 342 73 819 973 184 508 131 351 342 576 179 397 23 523 926 684 73 479 722 973 80 576 397 301 508 903 618 672 192 33 903 973 885 523 661 885 8 787 988 647 990 393 211 722 586 751 926 960 322 179 131 131 988 196 342 508 351 672 342 644 926 990 819 301 80 73 397 104 131 678 3...
output:
6066915
result:
ok single line: '6066915'
Test #7:
score: 0
Accepted
time: 19ms
memory: 8736kb
input:
1000 1000 179 707 71 73 410 726 459 410 84 432 500 73 578 864 71 145 538 578 265 145 707 565 674 772 859 676 826 71 538 459 548 479 609 45 674 707 30 145 45 726 41 73 446 265 145 479 587 642 179 632 908 548 674 410 361 632 500 642 929 976 73 446 41 361 71 726 179 212 341 929 45 859 826 179 632 144 4...
output:
6242289
result:
ok single line: '6242289'
Test #8:
score: 0
Accepted
time: 18ms
memory: 12880kb
input:
1000 1000 146 917 487 589 225 927 972 449 969 728 99 288 615 564 728 146 880 561 563 745 442 880 118 392 634 564 636 917 442 738 280 254 225 710 254 449 221 564 394 969 556 99 634 589 976 301 117 487 561 867 98 880 392 880 917 819 556 634 941 969 653 927 972 615 146 819 969 98 653 941 809 699 590 30...
output:
9171879
result:
ok single line: '9171879'
Test #9:
score: 0
Accepted
time: 1ms
memory: 6592kb
input:
1000 1000 709 558 844 316 552 395 944 619 805 279 837 392 822 772 964 805 597 397 814 344 527 401 964 299 922 782 746 349 795 537 945 57 527 176 815 937 257 955 245 108 245 593 932 155 597 812 18 856 116 218 671 142 511 945 481 405 966 695 782 38 130 638 470 692 671 307 837 571 925 43 411 249 613 38...
output:
2186
result:
ok single line: '2186'
Test #10:
score: 0
Accepted
time: 2ms
memory: 8540kb
input:
1000 1000 833 350 567 76 488 416 350 135 874 275 555 996 263 152 14 380 409 442 672 836 490 5 421 901 781 875 135 209 162 442 6 47 111 180 317 162 876 368 393 656 712 535 583 976 918 591 29 887 436 599 702 5 512 778 901 111 423 591 274 599 686 655 2 656 444 172 836 800 865 920 3 19 781 375 157 683 8...
output:
2193
result:
ok single line: '2193'
Test #11:
score: 0
Accepted
time: 0ms
memory: 6488kb
input:
1000 1000 655 894 253 168 615 321 526 160 225 578 845 473 14 839 321 659 138 448 575 787 342 557 338 501 192 504 888 172 531 616 83 136 623 137 746 344 385 337 505 394 634 740 242 449 321 630 804 971 386 160 466 641 83 133 570 527 448 273 888 653 3 479 467 18 630 93 271 574 653 5 764 370 972 466 501...
output:
2159
result:
ok single line: '2159'
Test #12:
score: 0
Accepted
time: 1ms
memory: 6904kb
input:
1000 1000 210 626 59 74 95 486 328 63 894 222 908 764 299 197 871 600 954 241 431 660 816 997 186 34 737 604 889 568 454 115 61 933 417 221 279 971 333 340 143 374 168 409 426 50 875 423 86 413 805 719 222 319 461 864 244 679 49 220 98 579 329 737 568 926 328 330 694 445 318 480 576 748 242 989 968 ...
output:
2013
result:
ok single line: '2013'
Test #13:
score: 0
Accepted
time: 2ms
memory: 8620kb
input:
1000 1000 937 639 771 95 626 134 869 66 465 29 889 944 194 239 284 303 935 111 795 806 737 770 665 343 862 528 232 571 342 458 401 490 452 628 425 384 998 578 192 168 64 651 486 311 840 667 400 255 364 206 486 289 761 912 189 907 158 339 891 336 392 782 598 233 899 539 19 780 190 535 933 700 500 232...
output:
2004
result:
ok single line: '2004'
Test #14:
score: 0
Accepted
time: 1ms
memory: 6828kb
input:
1000 1000 568 607 217 544 12 124 766 801 924 290 957 218 816 552 913 189 982 916 896 289 304 74 426 190 844 543 849 972 386 59 626 472 869 838 234 581 232 707 623 685 873 344 295 496 352 557 314 35 329 432 155 422 803 322 42 735 36 760 249 306 706 533 748 161 887 911 872 64 440 450 662 607 274 659 7...
output:
2002
result:
ok single line: '2002'
Test #15:
score: 0
Accepted
time: 2ms
memory: 8876kb
input:
1000 1000 726 492 65 652 168 218 347 489 35 415 73 324 80 419 237 352 378 3 708 286 933 810 116 563 819 610 670 386 392 940 434 926 341 617 820 842 618 974 592 344 724 578 955 761 26 902 545 496 688 636 273 225 749 840 661 784 917 595 503 84 414 252 925 877 352 479 792 914 54 666 324 257 642 637 801...
output:
2002
result:
ok single line: '2002'
Test #16:
score: 0
Accepted
time: 2ms
memory: 8312kb
input:
1000 1000 344 107 264 268 28 38 211 260 741 682 654 885 607 213 610 296 869 556 685 269 996 929 61 370 804 605 786 570 41 448 104 549 245 166 36 84 265 135 704 409 60 299 895 645 868 140 3 483 448 341 778 460 930 13 796 688 936 751 808 458 859 502 918 43 920 287 680 976 918 172 378 156 962 834 635 3...
output:
2002
result:
ok single line: '2002'
Test #17:
score: 0
Accepted
time: 1ms
memory: 8368kb
input:
1000 1000 117 152 117 375 190 586 117 586 278 546 788 450 117 90 511 586 450 595 586 492 870 278 17 117 586 275 520 471 796 117 520 112 117 431 292 520 320 520 278 95 586 677 450 402 298 520 586 109 450 409 520 607 684 278 520 898 340 278 17 520 586 64 586 100 520 647 450 270 520 617 685 117 117 985...
output:
6290
result:
ok single line: '6290'
Test #18:
score: 0
Accepted
time: 2ms
memory: 7944kb
input:
1000 1000 88 346 534 200 881 661 869 23 35 869 26 785 158 785 881 981 835 881 88 466 88 559 760 88 905 869 869 672 869 256 945 534 881 664 905 30 631 868 536 124 869 271 712 88 534 30 513 785 785 902 491 869 869 868 505 869 488 897 905 144 88 513 785 536 785 599 303 905 534 869 158 897 384 905 236 9...
output:
132867
result:
ok single line: '132867'
Test #19:
score: 0
Accepted
time: 2ms
memory: 7860kb
input:
1000 1000 463 338 246 242 91 76 130 858 818 250 255 639 135 571 809 250 794 255 91 170 386 678 639 513 507 684 463 407 463 969 463 769 685 463 250 513 126 684 684 444 53 969 250 876 811 639 286 571 386 684 571 407 794 463 507 463 295 170 678 809 91 678 811 349 777 53 463 286 261 401 130 346 91 625 8...
output:
9143208
result:
ok single line: '9143208'
Test #20:
score: 0
Accepted
time: 9ms
memory: 8248kb
input:
1000 1000 624 79 120 926 418 455 310 792 116 165 688 185 34 792 985 129 884 79 624 847 356 494 79 785 15 891 792 455 274 554 891 518 453 116 792 188 356 57 884 669 926 940 608 673 847 884 884 455 871 985 418 15 185 926 871 608 78 145 554 494 356 669 129 792 624 129 274 79 284 129 688 116 940 650 884...
output:
119880110
result:
ok single line: '119880110'
Test #21:
score: 0
Accepted
time: 42ms
memory: 17252kb
input:
1000 780 456 159 722 862 983 491 946 335 159 379 516 983 330 823 491 335 607 645 910 379 538 872 823 456 518 840 414 456 507 453 910 872 456 461 235 607 340 379 379 20 351 491 946 159 159 722 840 116 823 679 840 594 10 983 910 10 125 594 777 116 760 516 20 840 909 491 516 862 872 838 228 760 517 679...
output:
511621042
result:
ok single line: '511621042'
Test #22:
score: 0
Accepted
time: 5ms
memory: 6244kb
input:
1000 528 760 566 75 156 566 600 566 478 156 216 582 489 395 712 75 955 930 81 344 216 395 930 380 172 156 172 616 142 81 582 75 493 81 925 996 712 771 55 996 760 771 25 712 600 600 634 210 478 56 55 380 700 87 380 55 210 955 930 771 566 142 712 719 930 582 771 87 582 700 344 925 760 318 489 707 489 ...
output:
589935502
result:
ok single line: '589935502'
Test #23:
score: 0
Accepted
time: 2ms
memory: 7936kb
input:
1000 300 794 991 641 688 983 652 689 863 762 458 997 526 553 102 114 924 997 648 114 16 652 102 289 553 794 16 762 652 691 289 991 983 693 689 688 693 553 326 233 326 326 641 458 114 353 102 648 326 353 326 924 526 693 458 526 114 762 553 458 326 233 410 326 762 353 689 641 924 410 924 326 997 693 3...
output:
33555406
result:
ok single line: '33555406'
Test #24:
score: 0
Accepted
time: 64ms
memory: 20772kb
input:
1000 1000 678 283 616 283 675 678 449 486 486 892 734 781 465 343 496 379 35 301 299 409 496 781 978 538 434 283 453 406 751 289 812 979 289 379 374 979 449 206 299 219 486 649 496 883 334 807 892 449 678 812 892 299 383 289 978 453 242 971 734 37 35 892 971 217 423 467 978 283 334 138 465 374 978 4...
output:
53556160
result:
ok single line: '53556160'
Test #25:
score: 0
Accepted
time: 2ms
memory: 7916kb
input:
1000 1000 78 443 134 843 114 831 45 245 630 312 985 457 813 702 431 78 572 646 362 749 190 195 248 197 739 312 749 346 104 620 646 848 792 362 646 243 460 630 190 399 617 457 396 195 151 749 568 243 19 565 19 721 551 630 168 437 630 31 96 157 329 621 869 758 329 550 261 749 620 630 212 431 646 758 7...
output:
103300
result:
ok single line: '103300'
Test #26:
score: 0
Accepted
time: 1ms
memory: 8244kb
input:
1000 999 702 735 84 611 593 671 901 43 512 383 394 247 341 663 434 17 857 142 885 287 759 533 257 982 713 234 75 661 272 242 577 797 570 271 948 478 890 593 113 469 425 72 943 513 452 937 611 291 928 50 261 776 872 469 208 10 855 987 510 190 16 785 562 815 901 965 34 895 790 368 948 511 442 457 798 ...
output:
3331
result:
ok single line: '3331'
Test #27:
score: 0
Accepted
time: 1ms
memory: 6448kb
input:
1000 1000 561 417 561 221 739 163 431 493 561 113 739 433 431 64 619 739 265 561 260 674 266 739 561 619 561 198 431 522 518 561 522 561 730 776 431 924 863 730 674 866 739 236 579 730 431 237 561 86 418 431 561 247 810 674 730 981 674 199 739 863 739 813 730 221 74 561 739 79 431 943 776 431 288 73...
output:
7128
result:
ok single line: '7128'
Test #28:
score: 0
Accepted
time: 2ms
memory: 8012kb
input:
1000 1000 33 910 133 738 274 738 703 511 818 349 452 882 33 589 751 882 243 980 3 511 349 415 222 415 620 312 415 749 162 980 243 3 818 118 980 312 483 862 511 12 882 703 563 862 929 289 749 738 88 3 929 3 452 620 274 415 582 593 749 620 563 164 34 620 952 33 7 452 620 818 818 703 582 186 582 903 96...
output:
34603935
result:
ok single line: '34603935'
Test #29:
score: 0
Accepted
time: 6ms
memory: 8028kb
input:
1000 990 255 105 147 35 153 337 754 337 179 683 570 807 850 545 147 672 337 705 447 748 781 864 604 294 781 147 35 82 570 604 474 54 296 748 683 563 193 718 864 105 255 147 296 683 147 748 672 54 228 186 296 222 186 604 186 563 545 746 89 513 754 296 82 447 474 35 604 447 781 850 683 186 705 147 337...
output:
442451836
result:
ok single line: '442451836'
Test #30:
score: 0
Accepted
time: 3ms
memory: 6200kb
input:
1000 1000 718 915 120 276 503 601 798 754 81 338 537 83 857 331 718 461 338 651 915 429 915 408 814 375 718 897 871 355 207 603 494 331 52 563 116 81 814 674 857 537 289 81 718 871 81 909 929 375 537 573 537 658 725 364 402 814 573 120 754 333 331 674 537 601 798 338 563 227 871 289 364 429 857 923 ...
output:
603980708
result:
ok single line: '603980708'
Test #31:
score: 0
Accepted
time: 2ms
memory: 6300kb
input:
1000 1000 958 768 706 122 253 922 629 958 931 413 283 860 188 567 766 729 269 231 965 288 743 207 991 207 61 965 522 520 567 164 231 691 164 915 723 992 588 389 498 967 936 279 766 207 36 946 339 989 218 183 132 99 70 202 634 971 860 848 663 848 663 158 669 405 13 207 983 231 221 740 882 967 140 253...
output:
96119
result:
ok single line: '96119'
Test #32:
score: 0
Accepted
time: 1ms
memory: 6552kb
input:
1000 1000 538 269 110 87 434 7 892 344 432 612 700 505 795 647 82 323 339 395 849 499 755 165 833 55 720 356 612 66 898 257 922 276 729 162 395 883 840 629 886 668 278 735 394 859 677 156 435 805 474 339 92 140 832 764 233 26 192 635 165 784 138 417 585 474 278 619 739 82 154 651 884 503 504 883 575...
output:
4727
result:
ok single line: '4727'
Test #33:
score: 0
Accepted
time: 2ms
memory: 8256kb
input:
1000 1000 856 285 780 619 299 191 355 538 339 369 440 573 458 865 853 170 1 984 387 500 656 704 783 255 596 773 767 300 819 533 39 474 455 741 3 884 525 253 852 483 186 488 807 255 781 364 173 514 145 317 146 584 98 585 752 182 88 763 806 828 492 921 775 50 963 40 657 49 742 157 452 832 344 20 793 1...
output:
2499
result:
ok single line: '2499'
Test #34:
score: 0
Accepted
time: 0ms
memory: 6752kb
input:
1000 999 225 313 436 33 227 970 316 147 255 623 774 491 98 448 416 945 498 479 452 440 649 108 71 669 269 172 978 892 804 486 626 904 940 212 35 189 78 957 680 328 791 68 587 99 69 313 583 910 14 558 376 219 428 144 370 337 154 49 297 885 964 473 308 56 953 507 981 602 9 666 757 238 809 370 283 133 ...
output:
1999
result:
ok single line: '1999'
Test #35:
score: 0
Accepted
time: 161ms
memory: 47016kb
input:
1000 990 534 306 192 420 625 205 266 815 371 257 541 312 312 554 526 986 257 794 809 266 156 137 767 266 192 767 541 870 649 625 554 454 809 792 1000 378 46 526 792 985 306 554 755 957 541 957 1000 257 720 809 153 205 796 306 985 306 870 454 274 794 794 901 986 937 96 720 306 156 796 794 635 837 23 ...
output:
807527901
result:
ok single line: '807527901'
Test #36:
score: 0
Accepted
time: 100ms
memory: 19864kb
input:
1000 1000 672 525 486 525 521 469 649 109 254 553 163 517 34 773 37 553 561 34 37 578 746 811 250 811 517 360 822 922 566 652 822 378 521 922 612 597 305 561 935 240 109 120 811 578 694 797 935 387 517 561 935 649 797 264 612 594 746 120 944 897 649 705 974 710 566 561 974 797 944 240 378 264 822 79...
output:
513746449
result:
ok single line: '513746449'
Test #37:
score: 0
Accepted
time: 46ms
memory: 14192kb
input:
1000 1000 403 894 280 779 618 403 859 474 619 606 403 647 824 918 833 257 838 937 482 824 478 838 779 85 645 85 474 824 894 734 779 618 403 522 740 789 918 619 257 2 318 712 278 897 478 318 695 606 894 214 449 859 736 918 858 824 62 214 736 860 647 736 264 736 918 897 618 789 695 62 354 712 918 838 ...
output:
95754463
result:
ok single line: '95754463'
Test #38:
score: 0
Accepted
time: 25ms
memory: 12468kb
input:
1000 1000 833 152 949 597 833 343 65 925 618 744 758 919 175 70 858 534 328 526 398 271 994 318 814 175 744 614 758 483 152 70 249 814 919 343 597 246 233 837 744 526 236 249 710 1 23 660 246 373 614 19 334 999 70 343 614 221 70 23 236 919 534 221 858 949 221 233 999 814 65 758 328 236 363 925 814 7...
output:
5693083
result:
ok single line: '5693083'
Test #39:
score: 0
Accepted
time: 204ms
memory: 47408kb
input:
1000 990 22 39 24 2 39 41 44 39 41 5 38 4 19 30 40 27 24 16 7 22 28 34 32 17 32 4 44 6 27 22 6 33 43 30 45 7 46 35 45 20 42 11 10 27 3 1 26 19 7 25 32 39 12 30 1 41 18 7 9 13 14 7 12 40 4 18 10 32 1 13 37 22 12 10 33 42 34 15 11 9 9 43 24 45 8 10 32 42 41 28 6 23 24 40 19 15 37 27 30 9 32 20 35 17 1...
output:
807527901
result:
ok single line: '807527901'
Test #40:
score: 0
Accepted
time: 81ms
memory: 20420kb
input:
1000 1000 29 32 10 3 8 19 18 5 1 35 36 33 37 9 24 34 38 14 2 16 8 15 34 27 38 16 45 28 26 17 38 9 41 8 9 34 13 9 41 46 45 26 18 24 7 30 4 44 15 36 37 25 30 13 27 37 36 2 25 28 19 6 18 21 4 17 21 1 1 30 30 46 27 13 11 6 42 15 14 22 37 35 5 37 1 47 13 3 22 42 36 3 35 47 12 17 45 5 31 18 23 20 5 35 46 ...
output:
654727113
result:
ok single line: '654727113'
Test #41:
score: 0
Accepted
time: 199ms
memory: 46976kb
input:
1000 990 40 5 36 31 20 33 5 25 29 17 42 27 23 18 31 39 38 20 38 45 11 23 46 43 21 24 27 23 2 15 15 21 37 4 36 1 10 26 13 17 37 30 31 44 20 16 2 23 12 40 34 20 6 11 1 5 27 9 6 12 15 19 37 44 1 27 14 2 22 24 36 21 14 45 40 1 22 46 16 33 40 27 46 15 29 31 39 25 34 17 42 23 12 45 16 29 31 13 8 46 42 15 ...
output:
807527901
result:
ok single line: '807527901'
Test #42:
score: 0
Accepted
time: 99ms
memory: 20880kb
input:
1000 1000 34 22 7 19 40 45 29 34 26 41 9 24 15 25 26 37 41 4 22 41 25 11 16 32 28 21 45 34 12 34 8 4 26 2 28 42 31 12 36 29 4 28 2 19 37 19 18 31 46 43 35 43 47 20 5 32 23 30 7 42 47 33 2 38 18 20 35 31 13 26 9 27 24 21 11 16 38 41 8 30 46 13 18 40 33 20 45 13 16 47 21 34 12 37 28 43 10 23 14 35 22 ...
output:
561952342
result:
ok single line: '561952342'
Test #43:
score: 0
Accepted
time: 118ms
memory: 32748kb
input:
44 924 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 2 11 2 12 2 13 2 14 2 15 2 16 2 17 2 18 2 19 2 20 2 21 2 22 3 4 3 5 3 6 3 7 3 8 3 9 3 10 3 11 3 12 3 13 3 14 3 15 3 16 3 17 3 18 3 19 3 20 3 21 3 22 4 5 4 6 4 7 4 ...
output:
381059391
result:
ok single line: '381059391'