QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#334996#7925. ChayasSTnofarjo#TL 5816ms1969908kbC++172.1kb2024-02-22 16:01:202024-02-22 16:01:20

Judging History

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

  • [2024-02-22 16:01:20]
  • 评测
  • 测评结果：TL
  • 用时：5816ms
  • 内存：1969908kb
查看
  • [2024-02-22 16:01:20]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int maxn = 24, maxm = maxn * maxn * maxn, mod = 998244353;
int n, m;
int a[maxm], b[maxm], c[maxm];
set<vector<int>> st;
bool invalid[1<<maxn][maxn];
int dp[1<<maxn][maxn];
int ans;

int cut(int mask, int l, int r) {
	return (mask >> l) & ((1 << (r-l+1)) - 1);
}

void modadd(int &a, int b) {
	a += b;
	if (a >= mod) a -= mod;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	for (int i=0; i<m; i++) {
		cin >> a[i] >> b[i] >> c[i];
		a[i]--, b[i]--, c[i]--;
	}

	for (int i=0; i<m; i++) {
		vector<int> abc = {a[i], b[i], c[i]};
		sort(abc.begin(), abc.end());
		if (st.count(abc)) {
			cout << "0\n";
			return 0;
		}
		st.insert(abc);
	}

	memset(invalid, false, sizeof invalid);
	for (int i=0; i<m; i++) {

		// gaboleh ke b kalo a dan c sama
		vector<int> srt = {a[i], b[i], c[i]};
		sort(srt.begin(), srt.end());
		for (int mask=0; mask<(1<<(n-3)); mask++) {
			int true_mask = 0;

			if (srt[0] > 0) true_mask |= cut(mask, 0, srt[0] - 1);
			if (srt[0] + 1 <= srt[1] - 1) true_mask |= (cut(mask, srt[0], srt[1] - 2) << (srt[0] + 1));
			if (srt[1] + 1 <= srt[2] - 1) true_mask |= (cut(mask, srt[1] - 1, srt[2] - 3) << (srt[1] + 1));
			if (srt[2] + 1 <= n - 1) true_mask |= (cut(mask, srt[2] - 2, n - 4) << (srt[2] + 1));
			invalid[true_mask][b[i]] = true;

			true_mask |= (1 << a[i]);
			true_mask |= (1 << c[i]);
			invalid[true_mask][b[i]] = true;
		}
	}

	memset(dp, 0, sizeof dp);
	for (int mask=1; mask<(1<<n); mask++) {
		if ((mask&(mask-1)) == 0) {
			int i = 31 - __builtin_clz(mask);
			dp[mask][i] = (!invalid[0][i]); // cek dulu i pernah jadi b atau nggak
		} else {
			vector<int> ons;
			for (int i=0; i<n; i++) {
				if ((mask >> i) & 1) ons.push_back(i);
			}
			for (int i : ons) {
				for (int j : ons) {
					if (i == j) continue;
					int pre_mask = mask & ~(1 << j);
					if (!invalid[pre_mask][j]) modadd(dp[mask][j], dp[pre_mask][i]);
				}
			}
		}
	}

	ans = 0;
	for (int i=0; i<n; i++) modadd(ans, dp[(1<<n)-1][i]);
	cout << ans << '\n';
}
源文件, 语言: C++17

详细

Test #1:

score: 100
Accepted
time: 55ms
memory: 1969620kb

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

input:

4 2
3 1 4
1 4 3

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 56ms
memory: 1969696kb

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: 55ms
memory: 1969576kb

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: 44ms
memory: 1969608kb

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: 67ms
memory: 1969908kb

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: 63ms
memory: 1969860kb

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: 739ms
memory: 1969892kb

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: 1272ms
memory: 1969728kb

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: 2993ms
memory: 1969700kb

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: 5816ms
memory: 1969700kb

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 繁體中文 简体中文

服务器时间: 2024-12-12 01:58:55 | 开源项目