QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#864347 | #7514. Clique Challenge | msk_sama | WA | 0ms | 8068kb | C++14 | 2.3kb | 2025-01-20 15:08:28 | 2025-01-20 15:08:28 |
Judging History
answer
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cstdio>
#include <vector>
#include <cassert>
#include <cstring>
#include <algorithm>
#define fi first
#define se second
#define ep emplace
#define MISAKA main
#define ll long long
#define eb emplace_back
#define pii pair<int,int>
#define rg(x) x.begin(),x.end()
#define pc(x) __builtin_popcount(x)
#define mems(a,x) memset(a,x,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _rep(i,a,b) for(int i=(a);i>=(b);--i)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define FIO(FILE) freopen(FILE".in","r",stdin),freopen(FILE".out","w",stdout)
using namespace std;
bool __st;
inline int read(){
char c=getchar();int f=1,x=0;
for(;c<48||c>57;c=getchar())if(c=='-') f=-1;
for(;47<c&&c<58;c=getchar()) x=(x<<3)+(x<<1)+(c^48);
return x*f;
}
const int N=1010,mod=1e9+7;
int n,m,deg[N],r[N],mp[N][N],f[1<<20],lg[1<<20],ans;
vector<int> g[N],G[N];
void misaka(){
n=read(),m=read();
rep(i,1,m){
int u=read(),v=read();
if(mp[u][v]) continue;
deg[u]++,deg[v]++;
G[u].eb(v);
mp[u][v]=mp[v][u]=1;
}
rep(u,1,n)for(int v:G[u]){
if(deg[u]<deg[v]||(deg[u]==deg[v]&&u<v)) g[u].eb(v);
else g[v].eb(u);
}
rep(i,0,19) lg[1<<i]=i;
rep(u,1,n){
if(g[u].size()==0){ans++;continue;}
if(g[u].size()==1){ans+=2;continue;}
int k=g[u].size(),p=k>>1,q=k-p,sum=1;
rep(i,0,(1<<p)-1) f[i]=0;
rep(i,0,k-1){
int v=g[u][i];r[i]=0;
rep(j,0,p-1) r[i]|=(mp[v][g[u][j]]^1)<<j;
}
f[0]=1;
rep(i,1,(1<<p)-1){
int x=lg[i&-i];
f[i]=(f[i^(1<<x)]+f[i^r[x]])%mod;
}
rep(i,0,(1<<q)-1){
int s=0;
rep(j,0,q-1)if(i>>j&1) s|=r[j+p];
((sum+=f[((1<<p)-1)^s])>=mod)&&(sum-=mod);
if(!i) sum--;
}
(ans+=sum)%=mod;
if(ans<0) ans+=mod;
}
printf("%d",ans%mod);
}
bool __ed;
signed MISAKA(){
#ifdef LOCAL_MSK
atexit([](){
debug("\n%.3lfs ",(double)clock()/CLOCKS_PER_SEC);
debug("%.3lfMB\n",abs(&__st-&__ed)/1024./1024);});
#endif
int T=1;
while(T--) misaka();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 5928kb
input:
3 2 1 2 2 3
output:
5
result:
ok single line: '5'
Test #2:
score: 0
Accepted
time: 0ms
memory: 7976kb
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: 8068kb
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:
1475
result:
wrong answer 1st lines differ - expected: '1373', found: '1475'