QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#772122#7196. Perfect MatchingwtcTL 1691ms42900kbC++14659b2024-11-22 17:08:132024-11-22 17:08:14

Judging History

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

  • [2024-11-22 17:08:14]
  • 评测
  • 测评结果：TL
  • 用时：1691ms
  • 内存：42900kb
查看
  • [2024-11-22 17:08:13]
  • 提交

answer

#include<bits/stdc++.h>
#define fo(i,l,r) for(int i=(l);i<=(r);++i)
#define fd(i,l,r) for(int i=(l);i>=(r);--i)
#define fu(i,l,r) for(int i=(l);i<(r);++i)
#define ll long long
using namespace std;
const int N=33,mo=1e9+7;
int n,m,e[N][N];
map<int,int>mp;
void add(int &x,int y){x+=y;if(x>=mo)x-=mo;}
int dfs(int x)
{
	if(!x) return 1;
	if(mp.count(x)) return mp[x];
	int y=x&(x-1),s=0;
	int z=__builtin_ctz(x);
	fu(i,z+1,n) if(((y>>i)&1)&&e[z][i]) add(s,dfs(y^(1<<i)));
	return mp[x]=s;
}
int main()
{
	scanf("%d%d",&n,&m);
	fo(i,1,m)
	{
		int x,y;scanf("%d%d",&x,&y);x--;y--;
		e[x][y]=e[y][x]=1;
	}
	printf("%d",dfs((1<<n)-1));
}
源文件, 语言: C++14

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3688kb

input:

4 4
1 3
1 4
2 3
2 4

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

4 6
1 2
1 3
1 4
2 3
2 4
3 4

output:

3

result:

ok 1 number(s): "3"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3896kb

input:

1 0

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

1 0

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3708kb

input:

2 1
2 1

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3708kb

input:

4 5
4 2
2 3
3 1
1 4
3 4

output:

2

result:

ok 1 number(s): "2"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

8 18
8 7
4 3
4 8
5 3
3 6
2 5
6 2
8 6
7 3
4 7
1 2
3 8
2 3
8 5
1 7
7 6
1 6
8 1

output:

15

result:

ok 1 number(s): "15"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3988kb

input:

16 91
9 12
8 14
5 2
4 12
11 16
7 9
8 16
4 10
6 15
9 14
10 16
15 7
15 16
11 12
11 10
10 2
11 13
8 1
5 14
16 3
13 3
5 10
7 10
15 11
11 2
6 9
1 7
7 3
2 8
6 7
9 16
11 9
4 3
16 1
15 2
6 5
16 12
3 15
13 14
7 16
9 1
9 2
1 14
15 14
10 1
10 9
16 14
16 4
2 14
6 12
5 8
11 1
1 4
1 5
6 14
12 7
10 15
12 2
12 5
1 ...

output:

222058

result:

ok 1 number(s): "222058"

Test #9:

score: 0
Accepted
time: 1691ms
memory: 42900kb

input:

29 303
13 22
17 7
21 13
29 26
3 23
24 29
11 9
17 3
25 28
19 8
25 9
22 2
4 11
23 10
24 27
23 20
8 9
6 9
20 15
22 4
1 19
15 16
25 5
17 16
1 5
22 18
10 7
8 26
29 17
27 15
29 10
13 28
17 11
8 13
29 2
9 15
1 10
8 23
6 26
28 14
4 8
1 20
2 21
14 15
24 11
11 22
27 19
7 22
25 12
26 3
7 12
15 4
22 26
4 29
16 ...

output:

0

result:

ok 1 number(s): "0"

Test #10:

score: 0
Accepted
time: 6ms
memory: 4212kb

input:

20 150
20 3
17 8
5 11
20 11
12 9
15 1
3 18
19 11
4 10
8 7
1 13
13 9
14 9
1 20
3 16
16 4
14 15
1 8
5 14
16 12
8 9
2 19
3 15
13 7
19 13
20 14
10 9
1 6
6 15
20 2
13 20
18 2
8 11
5 16
19 8
1 14
13 6
1 19
15 18
20 5
14 8
1 12
10 18
3 4
4 20
13 10
8 5
12 7
5 13
1 7
16 7
15 4
14 6
10 12
11 1
11 13
15 7
9 1...

output:

55571531

result:

ok 1 number(s): "55571531"

Test #11:

score: 0
Accepted
time: 11ms
memory: 4468kb

input:

20 164
2 10
5 9
8 2
2 14
17 2
10 13
12 2
8 9
1 12
15 14
15 3
4 1
16 5
6 7
5 7
13 9
18 13
9 16
8 13
1 11
20 18
16 6
4 19
10 7
20 3
8 17
4 20
15 11
3 7
8 18
10 15
10 5
16 8
19 15
18 2
7 2
18 3
11 9
15 17
18 6
12 4
7 19
1 15
4 13
8 4
9 6
11 5
12 3
12 8
1 10
2 3
8 10
5 17
20 11
15 4
16 13
19 8
8 14
17 1...

output:

144711801

result:

ok 1 number(s): "144711801"

Test #12:

score: 0
Accepted
time: 11ms
memory: 4412kb

input:

20 187
18 5
16 9
1 6
6 12
20 14
1 5
2 20
15 12
16 6
13 8
9 4
15 13
6 10
18 15
18 9
5 14
13 1
2 4
9 12
12 8
18 7
19 12
14 12
6 17
11 3
20 8
3 6
20 11
5 10
11 10
3 2
7 4
19 2
11 5
16 17
4 10
15 20
8 11
7 8
13 14
3 8
7 20
16 2
11 4
5 19
5 3
14 10
20 17
20 13
20 3
10 9
11 15
17 19
1 12
2 11
11 1
13 17
1...

output:

555404850

result:

ok 1 number(s): "555404850"

Test #13:

score: 0
Accepted
time: 12ms
memory: 4408kb

input:

20 190
9 5
4 19
14 2
16 1
1 13
11 5
3 11
8 17
3 1
15 18
8 13
18 11
19 16
10 20
6 11
14 8
1 8
3 4
14 19
14 9
13 6
1 2
16 9
4 15
12 19
9 3
15 9
5 20
12 18
8 11
8 5
8 9
14 7
5 6
6 3
8 15
11 16
6 12
10 17
20 8
6 18
1 9
19 18
10 11
3 7
5 13
10 3
19 17
7 19
1 4
16 18
18 17
19 13
7 6
5 10
17 3
4 5
2 20
12 ...

output:

654729075

result:

ok 1 number(s): "654729075"

Test #14:

score: 0
Accepted
time: 12ms
memory: 4336kb

input:

20 190
1 8
4 2
5 6
12 15
11 6
1 4
4 9
18 4
4 20
13 17
6 3
5 19
1 6
9 3
1 3
4 19
16 10
15 5
2 11
8 20
9 15
18 17
10 11
1 17
19 13
8 5
12 18
15 3
9 11
13 14
17 14
18 8
19 9
19 10
6 16
18 5
16 19
16 8
6 17
14 7
15 14
7 13
13 16
17 16
4 5
10 13
4 17
15 2
18 14
18 2
6 18
5 9
5 1
10 15
16 12
1 19
12 5
9 1...

output:

654729075

result:

ok 1 number(s): "654729075"

Test #15:

score: 0
Accepted
time: 12ms
memory: 4428kb

input:

20 190
15 14
7 9
18 10
7 6
9 19
2 11
12 2
7 1
8 17
3 18
15 20
1 20
10 2
14 12
9 17
8 9
7 10
6 3
6 8
14 20
5 10
16 4
1 13
12 11
7 4
8 2
10 19
15 7
13 15
1 4
15 6
20 12
13 12
7 14
20 8
4 18
9 13
11 1
4 5
14 16
6 5
10 3
1 17
9 18
9 12
3 20
1 9
18 11
2 14
8 13
2 5
5 3
6 18
10 12
12 6
20 7
16 18
14 18
4 ...

output:

654729075

result:

ok 1 number(s): "654729075"

Test #16:

score: -100
Time Limit Exceeded

input:

30 339
20 19
30 19
20 18
27 11
13 25
20 30
3 30
11 16
29 17
25 12
28 30
10 25
1 13
26 24
12 7
13 17
19 7
22 7
8 16
30 5
2 29
19 26
5 13
29 23
4 13
15 13
17 6
12 13
19 11
11 9
8 2
23 22
5 2
20 15
15 4
3 1
10 14
13 24
10 22
22 18
22 1
22 15
8 21
10 3
24 8
4 6
19 9
13 27
20 6
3 6
7 16
22 4
26 29
25 4
2...

output:

result:
English 繁體中文 简体中文

服务器时间: 2024-12-05 00:01:22 | 开源项目