QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#295474	#7514. Clique Challenge	sofija6	TL	616ms	24072kb	C++23	3.2kb	2023-12-31 08:23:03	2023-12-31 08:23:04

Judging History

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

[2023-12-31 08:23:04]
评测

测评结果：TL
用时：616ms
内存：24072kb

查看

[2023-12-31 08:23:03]
提交

answer

#include <bits/stdc++.h>
#define ll long long
#define MAXN 1010
#define MAXS (1<<26)
#define MOD 1000000007
using namespace std;
vector<ll> G[MAXN];
bool act[MAXN],dpl[MAXS],dpr[MAXS],edge[MAXN][MAXN];
ll sum[MAXS],mask1[MAXS];
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,m,u,v;
    cin >> n >> m;
    for (ll i=1;i<=m;i++)
    {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
        edge[u][v]=edge[v][u]=true;
    }
    for (ll i=1;i<=n;i++)
        act[i]=true;
    ll cnt=n,ans=0;
    while (cnt)
    {
        vector<pair<ll,ll> > deg;
        for (ll i=1;i<=n;i++)
        {
            if (act[i])
            {
                ll c=0;
                for (ll next : G[i])
                    c+=act[next];
                deg.push_back({c,i});
            }
        }
        sort(deg.begin(),deg.end());
        u=deg[0].second;
        act[u]=false;
        cnt--;
        vector<ll> w,l,r;
        for (ll next : G[u])
        {
            if (act[next])
                w.push_back(next);
        }
        for (ll i=0;i<w.size()/2;i++)
            l.push_back(w[i]);
        for (ll i=w.size()/2;i<w.size();i++)
            r.push_back(w[i]);
        for (ll i=0;i<(1<<l.size());i++)
            dpl[i]=true;
        for (ll i=0;i<(1<<r.size());i++)
            dpr[i]=true;
        ll m[l.size()+5]={0};
        for (ll i=0;i<l.size();i++)
        {
            for (ll j=0;j<r.size();j++)
            {
                if (!edge[l[i]][r[j]])
                    m[i]+=(1<<j);
            }
        }
        for (ll i=1;i<(1<<l.size());i++)
        {
            ll pos;
            for (ll j=0;j<l.size();j++)
            {
                if ((1<<j)&i)
                    pos=j;
            }
            for (ll j=0;j<l.size();j++)
            {
                if ((1<<j)&i && j!=pos && !edge[l[j]][l[pos]])
                    dpl[i]=false;
            }
            dpl[i]=(dpl[i] && dpl[i^(1<<pos)]);
            mask1[i]=mask1[i^(1<<pos)]|m[pos];
        }
        for (ll i=1;i<(1<<r.size());i++)
        {
            ll pos;
            for (ll j=0;j<r.size();j++)
            {
                if ((1<<j)&i)
                    pos=j;
            }
            for (ll j=0;j<r.size();j++)
            {
                if ((1<<j)&i && j!=pos && !edge[r[j]][r[pos]])
                    dpr[i]=false;
            }
            dpr[i]=(dpr[i] && dpr[i^(1<<pos)]);
        }
        for (ll i=0;i<(1<<r.size());i++)
            sum[i]=dpr[i];
        for (ll i=0;i<r.size();i++)
        {
            for (ll j=0;j<(1<<r.size());j++)
            {
                if (j&(1<<i))
                    sum[j]+=sum[j^(1<<i)];
                if (sum[j]>=MOD)
                    sum[j]%=MOD;
            }
        }
        for (ll i=0;i<(1<<l.size());i++)
        {
            if (!dpl[i])
                continue;
            ll mask=(1<<r.size())-1;
            mask^=(mask&mask1[i]);
            ans+=sum[mask];
            if (ans>=MOD)
                ans%=MOD;
        }
    }
    cout << ans;
    return 0;
}

源文件, 语言: C++23

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 9616kb

input:

3 2
1 2
2 3

output:

result:

ok single line: '5'

Test #2:

score: 0

Accepted

time: 0ms

memory: 5588kb

input:

output:

result:

ok single line: '7'

Test #3:

score: 0

Accepted

time: 16ms

memory: 7648kb

input:

output:

result:

ok single line: '1373'

Test #4:

score: 0

Accepted

time: 209ms

memory: 9220kb

input:

output:

result:

ok single line: '6621319'

Test #5:

score: 0

Accepted

time: 226ms

memory: 10916kb

input:

output:

result:

ok single line: '6403686'

Test #6:

score: 0

Accepted

time: 209ms

memory: 9240kb

input:

output:

result:

ok single line: '6066915'

Test #7:

score: 0

Accepted

time: 193ms

memory: 9816kb

input:

output:

result:

ok single line: '6242289'

Test #8:

score: 0

Accepted

time: 174ms

memory: 7768kb

input:

output:

result:

ok single line: '9171879'

Test #9:

score: 0

Accepted

time: 13ms

memory: 5828kb

input:

output:

result:

ok single line: '2186'

Test #10:

score: 0

Accepted

time: 13ms

memory: 5716kb

input:

output:

result:

ok single line: '2193'

Test #11:

score: 0

Accepted

time: 14ms

memory: 5592kb

input:

output:

result:

ok single line: '2159'

Test #12:

score: 0

Accepted

time: 18ms

memory: 5968kb

input:

output:

result:

ok single line: '2013'

Test #13:

score: 0

Accepted

time: 24ms

memory: 5636kb

input:

output:

result:

ok single line: '2004'

Test #14:

score: 0

Accepted

time: 18ms

memory: 5936kb

input:

output:

result:

ok single line: '2002'

Test #15:

score: 0

Accepted

time: 23ms

memory: 7700kb

input:

output:

result:

ok single line: '2002'

Test #16:

score: 0

Accepted

time: 22ms

memory: 5880kb

input:

output:

result:

ok single line: '2002'

Test #17:

score: 0

Accepted

time: 14ms

memory: 7632kb

input:

output:

result:

ok single line: '6290'

Test #18:

score: 0

Accepted

time: 11ms

memory: 5636kb

input:

output:

result:

ok single line: '132867'

Test #19:

score: 0

Accepted

time: 11ms

memory: 7648kb

input:

output:

result:

ok single line: '9143208'

Test #20:

score: 0

Accepted

time: 82ms

memory: 6248kb

input:

output:

119880110

result:

ok single line: '119880110'

Test #21:

score: 0

Accepted

time: 431ms

memory: 20752kb

input:

output:

511621042

result:

ok single line: '511621042'

Test #22:

score: 0

Accepted

time: 45ms

memory: 6740kb

input:

output:

589935502

result:

ok single line: '589935502'

Test #23:

score: 0

Accepted

time: 17ms

memory: 7684kb

input:

output:

33555406

result:

ok single line: '33555406'

Test #24:

score: 0

Accepted

time: 616ms

memory: 24072kb

input:

output:

53556160

result:

ok single line: '53556160'

Test #25:

score: 0

Accepted

time: 11ms

memory: 5672kb

input:

output:

result:

ok single line: '103300'

Test #26:

score: 0

Accepted

time: 14ms

memory: 5828kb

input:

output:

result:

ok single line: '3331'

Test #27:

score: 0

Accepted

time: 12ms

memory: 5604kb

input:

output:

result:

ok single line: '7128'

Test #28:

score: 0

Accepted

time: 15ms

memory: 5656kb

input:

output:

34603935

result:

ok single line: '34603935'

Test #29:

score: 0

Accepted

time: 46ms

memory: 6128kb

input:

output:

442451836

result:

ok single line: '442451836'

Test #30:

score: 0

Accepted

time: 23ms

memory: 5860kb

input:

output:

603980708

result:

ok single line: '603980708'

Test #31:

score: 0

Accepted

time: 11ms

memory: 5740kb

input:

output:

result:

ok single line: '96119'

Test #32:

score: 0

Accepted

time: 13ms

memory: 5828kb

input:

output:

result:

ok single line: '4727'

Test #33:

score: 0

Accepted

time: 14ms

memory: 7684kb

input:

output:

result:

ok single line: '2499'

Test #34:

score: 0

Accepted

time: 14ms

memory: 6064kb

input:

output:

result:

ok single line: '1999'

Test #35:

score: -100

Time Limit Exceeded

input: