QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#329966	#7514. Clique Challenge	Register_int	AC ✓	65ms	69440kb	C++14	1.2kb	2024-02-17 10:04:07	2024-02-17 10:04:08

Judging History

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

[2024-02-17 10:04:08]
评测

测评结果：AC
用时：65ms
内存：69440kb

查看

[2024-02-17 10:04:07]
提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e3 + 10;

vector<int> G[MAXN]; int id[MAXN];

ll f[1 << 22], g[1 << 22], h[44];

inline 
ll solve(vector<int> &p) {
	memset(id, 0xff, sizeof id);
	int n = p.size(), l = n >> 1, r = n - l; ll ans = 0;
	for (int i = 0; i < n; i++) id[p[i]] = i, h[i] = 1ll << i;
	for (int i = 0; i < n; i++) for (int v : G[p[i]]) if (~id[v]) h[i] |= 1ll << id[v];
	*f = (1ll << n) - 1, *g = 1;
	for (int i = 0; i < l; i++) f[1 << i] = h[i];
	for (int i = 1; i < 1 << l; i++) f[i] = f[i & i - 1] & f[i & -i];
	for (int i = 1; i < 1 << r; i++) g[i] = g[i & i - 1] + g[h[__builtin_ctz(i) + l] >> l & i & i - 1];
	for (int i = 0; i < 1 << l; i++) if ((i & f[i]) == i) ans += g[f[i] >> l];
	return ans;
}

int n, m, d[MAXN]; vector<int> p; ll ans;

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1, u, v; i <= m; i++) {
		scanf("%d%d", &u, &v), d[u]++, d[v]++;
		G[u].push_back(v), G[v].push_back(u);
	}
	for (int u = 1; u <= n; u++) {
		p.push_back(u);
		for (int v : G[u]) if (d[u] < d[v] || (d[u] == d[v] && u < v)) p.push_back(v);
		ans += solve(p), p.clear();
	}
	printf("%lld", (ans >> 1) % 1000000007);
}

源文件, 语言: C++14

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

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 5812kb

input:

3 2
1 2
2 3

output:

result:

ok single line: '5'

Test #2:

score: 0

Accepted

time: 1ms

memory: 5844kb

input:

output:

result:

ok single line: '7'

Test #3:

score: 0

Accepted

time: 0ms

memory: 5852kb

input:

output:

result:

ok single line: '1373'

Test #4:

score: 0

Accepted

time: 3ms

memory: 11116kb

input:

output:

result:

ok single line: '6621319'

Test #5:

score: 0

Accepted

time: 4ms

memory: 13488kb

input:

output:

result:

ok single line: '6403686'

Test #6:

score: 0

Accepted

time: 7ms

memory: 10140kb

input:

output:

result:

ok single line: '6066915'

Test #7:

score: 0

Accepted

time: 3ms

memory: 11380kb

input:

output:

result:

ok single line: '6242289'

Test #8:

score: 0

Accepted

time: 6ms

memory: 12592kb

input:

output:

result:

ok single line: '9171879'

Test #9:

score: 0

Accepted

time: 1ms

memory: 5888kb

input:

output:

result:

ok single line: '2186'

Test #10:

score: 0

Accepted

time: 1ms

memory: 5956kb

input:

output:

result:

ok single line: '2193'

Test #11:

score: 0

Accepted

time: 0ms

memory: 5968kb

input:

output:

result:

ok single line: '2159'

Test #12:

score: 0

Accepted

time: 1ms

memory: 5840kb

input:

output:

result:

ok single line: '2013'

Test #13:

score: 0

Accepted

time: 1ms

memory: 5900kb

input:

output:

result:

ok single line: '2004'

Test #14:

score: 0

Accepted

time: 1ms

memory: 5980kb

input:

output:

result:

ok single line: '2002'

Test #15:

score: 0

Accepted

time: 1ms

memory: 5984kb

input:

output:

result:

ok single line: '2002'

Test #16:

score: 0

Accepted

time: 1ms

memory: 5960kb

input:

output:

result:

ok single line: '2002'

Test #17:

score: 0

Accepted

time: 1ms

memory: 6028kb

input:

output:

result:

ok single line: '6290'

Test #18:

score: 0

Accepted

time: 1ms

memory: 5844kb

input:

output:

result:

ok single line: '132867'

Test #19:

score: 0

Accepted

time: 1ms

memory: 5892kb

input:

output:

result:

ok single line: '9143208'

Test #20:

score: 0

Accepted

time: 3ms

memory: 6972kb

input:

output:

119880110

result:

ok single line: '119880110'

Test #21:

score: 0

Accepted

time: 9ms

memory: 22840kb

input:

output:

511621042

result:

ok single line: '511621042'

Test #22:

score: 0

Accepted

time: 0ms

memory: 10336kb

input:

output:

589935502

result:

ok single line: '589935502'

Test #23:

score: 0

Accepted

time: 0ms

memory: 6024kb

input:

output:

33555406

result:

ok single line: '33555406'

Test #24:

score: 0

Accepted

time: 14ms

memory: 30756kb

input:

output:

53556160

result:

ok single line: '53556160'

Test #25:

score: 0

Accepted

time: 1ms

memory: 5980kb

input:

output:

result:

ok single line: '103300'

Test #26:

score: 0

Accepted

time: 1ms

memory: 5876kb

input:

output:

result:

ok single line: '3331'

Test #27:

score: 0

Accepted

time: 1ms

memory: 5960kb

input:

output:

result:

ok single line: '7128'

Test #28:

score: 0

Accepted

time: 1ms

memory: 5952kb

input:

output:

34603935

result:

ok single line: '34603935'

Test #29:

score: 0

Accepted

time: 2ms

memory: 6472kb

input:

output:

442451836

result:

ok single line: '442451836'

Test #30:

score: 0

Accepted

time: 1ms

memory: 6012kb

input:

output:

603980708

result:

ok single line: '603980708'

Test #31:

score: 0

Accepted

time: 0ms

memory: 6040kb

input:

output:

result:

ok single line: '96119'

Test #32:

score: 0

Accepted

time: 0ms

memory: 5956kb

input:

output:

result:

ok single line: '4727'

Test #33:

score: 0

Accepted

time: 1ms

memory: 5964kb

input:

output:

result:

ok single line: '2499'

Test #34:

score: 0

Accepted

time: 0ms

memory: 5912kb

input:

output:

result:

ok single line: '1999'

Test #35:

score: 0

Accepted

time: 47ms

memory: 69364kb

input:

output:

807527901

result:

ok single line: '807527901'

Test #36:

score: 0

Accepted

time: 26ms

memory: 30796kb

input:

output:

513746449

result:

ok single line: '513746449'

Test #37:

score: 0

Accepted

time: 10ms

memory: 19728kb

input:

output:

95754463

result:

ok single line: '95754463'

Test #38:

score: 0

Accepted

time: 5ms

memory: 12408kb

input:

output:

result:

ok single line: '5693083'

Test #39:

score: 0

Accepted

time: 61ms

memory: 69440kb

input:

output:

807527901

result:

ok single line: '807527901'

Test #40:

score: 0

Accepted

time: 25ms

memory: 31560kb

input:

output:

654727113

result:

ok single line: '654727113'

Test #41:

score: 0

Accepted

time: 65ms

memory: 69360kb

input:

output:

807527901

result:

ok single line: '807527901'

Test #42:

score: 0

Accepted

time: 25ms

memory: 31432kb

input:

output:

561952342

result:

ok single line: '561952342'

Test #43:

score: 0

Accepted

time: 21ms

memory: 54996kb

input:

output:

381059391

result:

ok single line: '381059391'