QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#304921 | #7514. Clique Challenge | NemanjaSo2005 | WA | 0ms | 5640kb | C++14 | 2.7kb | 2024-01-14 06:20:00 | 2024-01-14 06:20:00 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll N,M;
ll res=0;
const int maxn=1e3+5;
const ll MOD=1e9+7;
bool povezan[maxn][maxn],bio[maxn];
vector<ll> graf[maxn];
ll mindeg(){
int koji=0;
for(int i=1;i<=N;i++)
if(!bio[i] and (graf[i].size()<graf[koji].size() or koji==0))
koji=i;
return koji;
}
vector<ll> V;
ll cmask[105],pmask[105],mid,vred[(1<<25)];
void rek1(ll gde,ll mask1,ll mask2){
if(gde==mid+1){
vred[mask2]++;
return;
}
rek1(gde+1,mask1,mask2);
if((cmask[gde]&mask1)==mask1)
rek1(gde+1,mask1|pmask[gde],mask2&cmask[gde]);
}
void rek2(ll gde,ll mask){
if(gde==V.size()){
// cout<<"KRAJ "<<mask<<endl;
res=res+vred[mask];
if(res>=MOD)
res-=MOD;
return;
}
rek2(gde+1,mask);
// cout<<mask<<" maske "<<cmask[gde]<<endl;
if((mask&cmask[gde])==mask)
rek2(gde+1,mask|pmask[gde]);
}
void resi(){
if(V.size()==0){
res++;
if(res>=MOD)
res-=MOD;
return;
}
if(V.size()==1){
res+=2;
if(res>=MOD)
res-=MOD;
return;
}
mid=V.size()/2-1;
for(ll i=0;i<=mid;i++)
pmask[i]=(1<<(30+i));
for(ll i=mid+1;i<V.size();i++)
pmask[i]=(1<<(i-mid-1));
for(ll i=0;i<V.size();i++)
for(ll j=0;j<V.size();j++)
if(povezan[V[i]][V[j]])
cmask[i]|=pmask[j];
for(ll i=0;i<=(1<<(V.size()-mid))-1;i++)
vred[i]=0;
rek1(0,0,(1<<(V.size()-mid))-1);
/*for(int i=0;i<16;i++){
cout<<i<<" "<<vred[i]<<endl;
}
cout<<endl;
*/
for(ll i=(1<<(V.size()-mid-1));i>=1;i>>=1){
for(ll j=(1<<(V.size()-mid))-1;j>=0;j--)
if(j&i)
vred[j^i]+=vred[j];
}
/* for(int i=0;i<16;i++){
cout<<i<<" "<<vred[i]<<endl;
}
cout<<endl;*/
rek2(mid+1,0);
}
int main(){/*
N=10;
M=N*(N-1)/2;
cout<<N<<" "<<M<<endl;
for(int i=1;i<=N;i++)
for(int j=i+1;j<=N;j++)
cout<<i<<" "<<j<<endl;
return 0;*/
cin>>N>>M;
int a,b;
while(M--){
cin>>a>>b;
povezan[a][b]=povezan[b][a]=true;
graf[a].push_back(b);
graf[b].push_back(a);
}
while(true){
int gde=mindeg();
if(gde==0)
break;
bio[gde]=true;
V=graf[gde];
resi();
graf[gde].clear();
for(int i=1;i<=N;i++){
if(graf[i].size()==0)
continue;
for(int j=0;j+1<graf[i].size();j++)
if(graf[i][j]==gde)
swap(graf[i][j],graf[i][j+1]);
if(graf[i].back()==gde)
graf[i].pop_back();
}
}
cout<<res<<"\n";
}
/*
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 5640kb
input:
3 2 1 2 2 3
output:
5
result:
ok single line: '5'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
3 3 1 2 1 3 2 3
output:
7
result:
ok single line: '7'
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3736kb
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:
1935
result:
wrong answer 1st lines differ - expected: '1373', found: '1935'