QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#574596#7925. Chayassea_birdTL 5218ms69208kbC++201.7kb2024-09-18 23:09:442024-09-18 23:09:44

Judging History

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

  • [2024-09-18 23:09:44]
  • 评测
  • 测评结果：TL
  • 用时：5218ms
  • 内存：69208kb
查看
  • [2024-09-18 23:09:44]
  • 提交

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];
int cnt = 0;
pii arr[10100];
int np[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;
    }
    // for (int i = 1; i <= n; i++) {
    //     for (int j = 1; j <= n; j++) {
    //         for (int k = 1; k <= n; k++) {
    //             g[i][j][k] = g[i][k][j] = g[i][j][k] | g[i][k][j];
    //         }
    //     }
    // }
    for (int a = 1; a <= n; a++) {
        for (int b = 1; b <= n; b++) {
            for (int c = 1; c <= n; c++) {
                if (g[c][a][b] or g[c][b][a]) {
                    np[a][b] |= (1 << (c - 1));
                }
            }
        }
    }
    f[0] = 1;
    for (int p = 0; p < (1 << n); p++) {
        int x = 0;
        for (int a = 1; a <= n; a++) {
            for (int b = 1; b <= n; b++) {
                if ((p & (1 << (a - 1))) and (!(p & (1 << (b - 1))))) {
                    x |= np[a][b];
                }
            }
        }
        for (int c = 1; c <= n; c++) {
            if (p & (1 << (c - 1)))
                continue;
            if (!(x & (1 << (c - 1)))) {
                f[p | (1 << (c - 1))] = (f[p | (1 << (c - 1))] + f[p]) % mod;
            }
        }
        // std::cout << f[p] << "\n";
    }
    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: 3660kb

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: 3660kb

input:

4 2
3 1 4
1 4 3

output:

0

result:

ok single line: '0'

Test #3:

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

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: 3604kb

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: 3608kb

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: 3692kb

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: 3688kb

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: 579ms
memory: 11900kb

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: 1175ms
memory: 20048kb

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: 0
Accepted
time: 2500ms
memory: 36376kb

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:

188168263

result:

ok single line: '188168263'

Test #11:

score: 0
Accepted
time: 5218ms
memory: 69208kb

input:

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

output:

131547430

result:

ok single line: '131547430'

Test #12:

score: -100
Time Limit Exceeded

input:

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

output:

result:
English 繁體中文 简体中文

Server Time: 2024-12-03 06:29:27 | OpenSource Project