QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #564309 | #7514. Clique Challenge | liujunyi123 | WA | 117ms | 56108kb | C++14 | 1.2kb | 2024-09-14 22:03:33 | 2024-09-14 22:03:34 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1005,M=(1<<23),mod=1e9+7;
int n,m,tot,ans,lg[M],d[N],E[N],E1[N],s1[M],s2[M],f[M],id[N],g[N][N];
vector<int> e[N],v1,v2;
void qm(int &x,int y){x+=y;if(x>=mod)x-=mod;}
int main(){
scanf("%d%d",&n,&m),lg[0]=-1;
for(int i=1;i<M;i++)lg[i]=lg[i>>1]+1;
for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),g[x][y]=g[y][x]=1,d[x]++,d[y]++;
for(int i=1;i<=n;i++){v1.clear(),v2.clear();
for(int j=1;j<=n;j++)if(g[i][j]&&(d[j]>d[i]||(d[j]==d[i]&&j>i))){
if(v1.size()<20)v1.push_back(j);
else v2.push_back(j);
}
for(int j=0;j<v1.size();j++)id[v1[j]]=j,E[j]=E1[j]=0;
for(int j=0;j<v2.size();j++)id[v2[j]]=j;
for(auto u:v1)for(auto v:v1)if(!g[u][v]&&u!=v)E[id[u]]|=(1<<id[v]),E[id[v]]|=(1<<id[u]);
for(auto u:v1)for(auto v:v2)if(!g[u][v])E1[id[u]]|=(1<<id[v]);
int tmp=(1<<v1.size())-1,tp2=(1<<v2.size())-1;
for(int s=0;s<=tmp;s++){
s1[s]=s2[s]=0;
if(s){
s1[s]=s1[s^(s&-s)]|E[lg[(s&-s)]];
s2[s]=s2[s^(s&-s)]|E1[lg[(s&-s)]];
}
if(!(s1[s]&s))f[tp2^E1[s]]++;
}
for(int j=0;j<v2.size();j++)
for(int s=0;s<=tp2;s++)if(!((s>>j)&1))qm(f[s],f[s^(1<<j)]);
for(int s=0;s<=tp2;s++)qm(ans,f[s]),f[s]=0;
}
printf("%d\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 7ms
memory: 44220kb
input:
3 2 1 2 2 3
output:
5
result:
ok single line: '5'
Test #2:
score: 0
Accepted
time: 6ms
memory: 43132kb
input:
3 3 1 2 1 3 2 3
output:
7
result:
ok single line: '7'
Test #3:
score: 0
Accepted
time: 5ms
memory: 44888kb
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: -100
Wrong Answer
time: 117ms
memory: 56108kb
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:
274632718
result:
wrong answer 1st lines differ - expected: '6621319', found: '274632718'