QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#574048#7925. Chayassea_birdTL 2879ms20072kbC++201.8kb2024-09-18 20:39:342024-09-18 20:39:39

Judging History

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

  • [2024-09-18 20:39:39]
  • 评测
  • 测评结果：TL
  • 用时：2879ms
  • 内存：20072kb
查看
  • [2024-09-18 20:39:34]
  • 提交

answer

#include<bits/stdc++.h>
typedef long long ll;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
const ll mod = 998244353;
ll f[1 << 24];
bool g[25][25][25];
bool fg[25][25];
void solve() {
    int n, m;
    std::cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        std::cin >> a >> b >> c;
        g[a][b][c] = true;
        g[c][b][a] = true;
    }
    f[0] = 1;
    for (int p = 0; p < (1 << n); p++) {
        for (int c = 1; c <= n; c++) {
            if (p & (1 << (c - 1)))
                continue;
            bool flag = true;
            for (int a = 1; a <= n; a++) {
                if (p & (1 << (a - 1))) {
                    for (int b = 1; b <= n; b++) {
                        if (g[c][b][a]) {
                            if (!(p & (1 << (b - 1)))) {
                                flag = false;
                                break;
                            }
                        }
                    }
                    if (!flag)
                        break;
                    for (int b = 1; b <= n; b++) {
                        if (g[c][a][b]) {
                            if (!(p & (1 << (b - 1)))) {
                                flag = false;
                                break;
                            }
                        }
                    }
                    if (!flag)
                        break;
                }
            }
            if (flag) {
                f[p | (1 << (c - 1))] = (f[p | (1 << (c - 1))] + f[p]) % mod;
            }
        }
    }
    std::cout << f[(1 << n) - 1] << "\n";
}
int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0), std::cout.tie(0);
    int t = 1;
    while (t--)solve();
    return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3748kb

input:

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

output:

4

result:

ok single line: '4'

Test #2:

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

input:

4 2
3 1 4
1 4 3

output:

0

result:

ok single line: '0'

Test #3:

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

input:

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

output:

2

result:

ok single line: '2'

Test #4:

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

input:

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

output:

6

result:

ok single line: '6'

Test #5:

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

input:

7 10
5 1 6
2 4 7
3 1 2
4 5 7
5 2 6
7 3 6
7 4 6
2 5 7
4 3 7
6 2 3

output:

8

result:

ok single line: '8'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3700kb

input:

9 12
8 1 5
6 1 2
4 2 3
2 9 3
1 6 3
7 9 5
4 2 8
3 8 2
6 7 3
4 2 7
3 7 1
7 5 2

output:

28

result:

ok single line: '28'

Test #7:

score: 0
Accepted
time: 2ms
memory: 3704kb

input:

12 15
10 8 7
2 10 9
4 9 3
5 2 6
7 12 10
10 3 5
4 6 10
9 11 1
12 4 6
8 1 3
6 11 2
3 2 11
4 6 1
4 6 11
7 4 5

output:

128

result:

ok single line: '128'

Test #8:

score: 0
Accepted
time: 1633ms
memory: 11936kb

input:

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

output:

115058708

result:

ok single line: '115058708'

Test #9:

score: 0
Accepted
time: 2879ms
memory: 20072kb

input:

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

output:

131696

result:

ok single line: '131696'

Test #10:

score: -100
Time Limit Exceeded

input:

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

output:

result:
English 繁體中文 简体中文

Server Time: 2024-12-03 04:33:46 | OpenSource Project