QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#200890	#7514. Clique Challenge	ucup-team1525	AC ✓	29ms	33780kb	C++17	1.6kb	2023-10-04 22:58:27	2023-10-04 22:58:27

Judging History

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

[2023-10-04 22:58:27]
评测

测评结果：AC
用时：29ms
内存：33780kb

查看

[2023-10-04 22:58:27]
提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e3,S=1<<22;
const int mod=1e9+7;
int add(int x,int y){ return (x+=y)>=mod?x-mod:x; }
int n,m;
int d[N+5],e[N+5][N+5];
int p[N+5];
int f[S+5],g[S+5];
vector<int> ver;
int e1[50],e2[50];
bool cmp(int x,int y){ return d[x]<d[y]; }
int solve(){
    int n1=ver.size()/2,n2=(ver.size()+1)/2;
    int ans=0;
    for(int i=0;i<n1+n2;i++){
        e1[i]=0;
        for(int j=0;j<n1;j++)
            if(e[ver[i]][ver[j]])
                e1[i]|=1<<j;
    }
    for(int i=n1;i<n1+n2;i++){
        e2[i]=0;
        for(int j=n1;j<n1+n2;j++)
            if(e[ver[i]][ver[j]])
                e2[i]|=1<<(j-n1);
    }
    f[0]=1;
    for(int i=1;i<(1<<n1);i++){
        int k=0; while(!(i>>k&1)) k++;
        f[i]=f[i^(1<<k)]+f[e1[k]&i];
    }
    fill(g,g+(1<<n2),0);
    g[0]=(1<<n1);
    for(int i=0;i<(1<<n2);i++){
        if(!g[i]) continue;
        g[i]--;
        ans=add(ans,f[g[i]]);
        for(int k=0;k<n2&&!(i>>k&1);k++)
            if((e2[k+n1]&i)==i) g[i|(1<<k)]=(g[i]&e1[k+n1])+1;
    }
    return ans;
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1,u,v;i<=m;i++){
        scanf("%d %d",&u,&v);
        e[u][v]=e[v][u]=1;
        d[u]++; d[v]++;
    }
    for(int i=1;i<=n;i++) p[i]=i;
    stable_sort(p+1,p+1+n,cmp);
    int ans=0;
    for(int i=1;i<=n;i++){
        ver.clear();
        for(int j=i+1;j<=n;j++)
            if(e[p[i]][p[j]]) ver.push_back(p[j]);
        sort(ver.begin(),ver.end());
        ans=add(ans,solve());
    }
    printf("%d\n",ans);
    return 0;
}

源文件, 语言: C++17

这程序好像有点Bug，我给组数据试试？

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 8132kb

input:

3 2
1 2
2 3

output:

result:

ok single line: '5'

Test #2:

score: 0

Accepted

time: 1ms

memory: 7880kb

input:

output:

result:

ok single line: '7'

Test #3:

score: 0

Accepted

time: 2ms

memory: 10040kb

input:

output:

result:

ok single line: '1373'

Test #4:

score: 0

Accepted

time: 3ms

memory: 12976kb

input:

output:

result:

ok single line: '6621319'

Test #5:

score: 0

Accepted

time: 3ms

memory: 14716kb

input:

output:

result:

ok single line: '6403686'

Test #6:

score: 0

Accepted

time: 5ms

memory: 11116kb

input:

output:

result:

ok single line: '6066915'

Test #7:

score: 0

Accepted

time: 5ms

memory: 10992kb

input:

output:

result:

ok single line: '6242289'

Test #8:

score: 0

Accepted

time: 0ms

memory: 9200kb

input:

output:

result:

ok single line: '9171879'

Test #9:

score: 0

Accepted

time: 2ms

memory: 10340kb

input:

output:

result:

ok single line: '2186'

Test #10:

score: 0

Accepted

time: 2ms

memory: 10416kb

input:

output:

result:

ok single line: '2193'

Test #11:

score: 0

Accepted

time: 2ms

memory: 10404kb

input:

output:

result:

ok single line: '2159'

Test #12:

score: 0

Accepted

time: 0ms

memory: 10352kb

input:

output:

result:

ok single line: '2013'

Test #13:

score: 0

Accepted

time: 2ms

memory: 10684kb

input:

output:

result:

ok single line: '2004'

Test #14:

score: 0

Accepted

time: 0ms

memory: 10636kb

input:

output:

result:

ok single line: '2002'

Test #15:

score: 0

Accepted

time: 2ms

memory: 10484kb

input:

output:

result:

ok single line: '2002'

Test #16:

score: 0

Accepted

time: 2ms

memory: 11116kb

input:

output:

result:

ok single line: '2002'

Test #17:

score: 0

Accepted

time: 0ms

memory: 10580kb

input:

output:

result:

ok single line: '6290'

Test #18:

score: 0

Accepted

time: 2ms

memory: 10124kb

input:

output:

result:

ok single line: '132867'

Test #19:

score: 0

Accepted

time: 0ms

memory: 10080kb

input:

output:

result:

ok single line: '9143208'

Test #20:

score: 0

Accepted

time: 3ms

memory: 10356kb

input:

output:

119880110

result:

ok single line: '119880110'

Test #21:

score: 0

Accepted

time: 13ms

memory: 17532kb

input:

output:

511621042

result:

ok single line: '511621042'

Test #22:

score: 0

Accepted

time: 2ms

memory: 10264kb

input:

output:

589935502

result:

ok single line: '589935502'

Test #23:

score: 0

Accepted

time: 2ms

memory: 10112kb

input:

output:

33555406

result:

ok single line: '33555406'

Test #24:

score: 0

Accepted

time: 11ms

memory: 19064kb

input:

output:

53556160

result:

ok single line: '53556160'

Test #25:

score: 0

Accepted

time: 2ms

memory: 10104kb

input:

output:

result:

ok single line: '103300'

Test #26:

score: 0

Accepted

time: 1ms

memory: 10232kb

input:

output:

result:

ok single line: '3331'

Test #27:

score: 0

Accepted

time: 2ms

memory: 10272kb

input:

output:

result:

ok single line: '7128'

Test #28:

score: 0

Accepted

time: 0ms

memory: 8164kb

input:

output:

34603935

result:

ok single line: '34603935'

Test #29:

score: 0

Accepted

time: 3ms

memory: 10092kb

input:

output:

442451836

result:

ok single line: '442451836'

Test #30:

score: 0

Accepted

time: 2ms

memory: 10304kb

input:

output:

603980708

result:

ok single line: '603980708'

Test #31:

score: 0

Accepted

time: 2ms

memory: 10128kb

input:

output:

result:

ok single line: '96119'

Test #32:

score: 0

Accepted

time: 2ms

memory: 10792kb

input:

output:

result:

ok single line: '4727'

Test #33:

score: 0

Accepted

time: 2ms

memory: 10380kb

input:

output:

result:

ok single line: '2499'

Test #34:

score: 0

Accepted

time: 2ms

memory: 11232kb

input:

output:

result:

ok single line: '1999'

Test #35:

score: 0

Accepted

time: 26ms

memory: 33780kb

input:

output:

807527901

result:

ok single line: '807527901'

Test #36:

score: 0

Accepted

time: 13ms

memory: 19600kb

input:

output:

513746449

result:

ok single line: '513746449'

Test #37:

score: 0

Accepted

time: 6ms

memory: 15232kb

input:

output:

95754463

result:

ok single line: '95754463'

Test #38:

score: 0

Accepted

time: 3ms

memory: 15096kb

input:

output:

result:

ok single line: '5693083'

Test #39:

score: 0

Accepted

time: 24ms

memory: 31760kb

input:

output:

807527901

result:

ok single line: '807527901'

Test #40:

score: 0

Accepted

time: 14ms

memory: 17048kb

input:

output:

654727113

result:

ok single line: '654727113'

Test #41:

score: 0

Accepted

time: 25ms

memory: 32244kb

input:

output:

807527901

result:

ok single line: '807527901'

Test #42:

score: 0

Accepted

time: 11ms

memory: 17856kb

input:

output:

561952342

result:

ok single line: '561952342'

Test #43:

score: 0

Accepted

time: 29ms

memory: 26272kb

input:

output:

381059391

result:

ok single line: '381059391'