QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#564212 | #7514. Clique Challenge | liujunyi123 | WA | 4ms | 24436kb | C++14 | 1.4kb | 2024-09-14 21:16:40 | 2024-09-14 21:16:40 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1005,M=(1<<22),mod=1e9+7;
int n,m,tot,ans,lg[M],d[N],E[N],E1[N],s1[M],s2[M],f[N],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);
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();
// cout<<" "<<i<<" "<<d[i]<<endl;
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);
// cout<<j<<" ";
}//cout<<endl;
for(int j=0;j<v1.size();j++)id[v1[j]]=j,E[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)]];
}
// cout<<s<<" "<<s1[s]<<" "<<s2[s]<<endl;
if(!(s1[s]&s))f[tp2^E1[s]]++;//cout<<tp2<<" "<<E1[s]<<endl;
}
for(int j=0;j<v2.size();i++)
for(int s=0;s<=tp2;s++)if(!((s>>j)&1))f[s]+=f[s^(1<<j)];
for(int s=0;s<=tp2;s++)qm(ans,f[s]),f[s]=0;
cout<<ans<<endl;
}
printf("%d\n",ans);
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 4ms
memory: 24436kb
input:
3 2 1 2 2 3
output:
2 3 5 5
result:
wrong answer 1st lines differ - expected: '5', found: '2'