QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #295679 | #7514. Clique Challenge | sofija6 | TL | 257ms | 16352kb | C++23 | 3.3kb | 2023-12-31 18:40:12 | 2023-12-31 18:40:13 |
Judging History
answer
#include <bits/stdc++.h>
#define ll int
#define MAXN 1010
#define MAXS (1<<25)
#define MOD 1000000007
using namespace std;
vector<ll> G[MAXN],l,r;
bool act[MAXN],dpl[MAXS],dpr[MAXS],edge[MAXN][MAXN];
ll sum[MAXS],mask1[MAXS],mm[25],deg[MAXN];
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
ll n,m,u,v;
cin >> n >> m;
for (ll i=1;i<=m;i++)
{
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
edge[u][v]=edge[v][u]=true;
deg[u]++;
deg[v]++;
}
for (ll i=1;i<=n;i++)
act[i]=true;
ll cnt=n;
ll ans=0;
dpl[0]=dpr[0]=true;
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > q;
for (ll i=1;i<=n;i++)
q.push({deg[i],i});
while (cnt)
{
ll minn=INT_MAX;
while (!act[q.top().second])
q.pop();
u=q.top().second;
minn=q.top().first;
q.pop();
act[u]=false;
cnt--;
l.clear();
r.clear();
for (ll next : G[u])
{
deg[next]--;
q.push({deg[next],next});
if (act[next])
{
if (l.size()<=14)
l.push_back(next);
else
r.push_back(next);
}
}
for (ll i=0;i<l.size();i++)
{
mm[i]=0;
for (ll j=0;j<r.size();j++)
{
if (!edge[l[i]][r[j]])
mm[i]+=(1<<j);
}
}
for (ll i=1;i<(1<<r.size());i++)
{
dpr[i]=true;
ll pos=-1;
for (ll j=0;j<r.size();j++)
{
if ((1<<j)&i)
{
if (pos==-1)
pos=j;
else if (!edge[r[j]][r[pos]])
{
dpr[i]=false;
break;
}
}
}
dpr[i]=(dpr[i] && dpr[i^(1<<pos)]);
}
for (ll i=0;i<(1<<r.size());i++)
sum[i]=dpr[i];
for (ll i=0;i<r.size();i++)
{
for (ll j=0;j<(1<<r.size());j++)
{
if (j&(1<<i))
sum[j]+=sum[j^(1<<i)];
if (sum[j]>=MOD)
sum[j]-=MOD;
}
}
for (ll i=1;i<(1<<l.size());i++)
{
dpl[i]=true;
ll pos=-1;
for (ll j=0;j<l.size();j++)
{
if ((1<<j)&i)
{
if (pos==-1)
pos=j;
else if (!edge[l[j]][l[pos]])
{
dpl[i]=false;
break;
}
}
}
dpl[i]=(dpl[i] && dpl[i^(1<<pos)]);
mask1[i]=mask1[i^(1<<pos)]|mm[pos];
if (dpl[i])
{
ll mask=(1<<r.size())-1;
mask^=(mask&mask1[i]);
ans+=sum[mask];
if (ans>=MOD)
ans-=MOD;
}
}
ans+=sum[(1<<r.size())-1];
}
cout << ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 11832kb
input:
3 2 1 2 2 3
output:
5
result:
ok single line: '5'
Test #2:
score: 0
Accepted
time: 0ms
memory: 9748kb
input:
3 3 1 2 1 3 2 3
output:
7
result:
ok single line: '7'
Test #3:
score: 0
Accepted
time: 1ms
memory: 9744kb
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: 257ms
memory: 16352kb
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: 230ms
memory: 16048kb
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: 210ms
memory: 16112kb
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: 168ms
memory: 14004kb
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: 156ms
memory: 14052kb
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: 0ms
memory: 11844kb
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: 0ms
memory: 11708kb
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: 2ms
memory: 9816kb
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: 0ms
memory: 9824kb
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: 1ms
memory: 9796kb
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: 0ms
memory: 9772kb
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: 1ms
memory: 9832kb
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: 0ms
memory: 9832kb
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: 2ms
memory: 11836kb
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: 8ms
memory: 11892kb
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: 85ms
memory: 11992kb
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: 82ms
memory: 10192kb
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: -100
Time Limit Exceeded
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...