QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#564212#7514. Clique Challengeliujunyi123WA 4ms24436kbC++141.4kb2024-09-14 21:16:402024-09-14 21:16:40

Judging History

你现在查看的是最新测评结果

  • [2024-09-14 21:16:40]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:24436kb
  • [2024-09-14 21:16:40]
  • 提交

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'