oj.uz

Submission #674490

# Submission time Handle Problem Language Result Execution time Memory
674490 2022-12-24T14:22:25 Z Sohsoh84 Cubeword (CEOI19_cubeword) C++17
84 / 100
 917 ms 429600 KB 
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

constexpr ll MAXN = 1e6 + 10;
constexpr ll MAXM = 26 + 26;
constexpr ll MOD = 998244353;

inline int f(char c) {
	if (c >= 'a' && c <= 'z') return c - 'a';
	else if (c >= 'A' && c <= 'Z') return c - 'A' + 26;
	return c - '0' + 26 + 26;
}

ll F[MAXM][MAXM], T[MAXM][MAXM][MAXM], ans;
int n, nxt[MAXN][MAXM], sz = 0;
vector<string> vec[MAXM];

inline bool add(string s) {
	int v = 0;
	bool flag = false;

	for (char c : s) {
		if (!nxt[v][f(c)]) {
			flag = true;
			nxt[v][f(c)] = ++sz;
		}

		v = nxt[v][f(c)];
	}

	return flag;
}

inline void solve(int len) {
	memset(F, 0, sizeof F);
	memset(T, 0, sizeof T);
	memset(nxt, 0, sizeof nxt);

	for (string s : vec[len])
		if (add(s))
			F[f(s.front())][f(s.back())]++;
	
	for (int i = 0; i < MAXM; i++)
		for (int j = 0; j < MAXM; j++)
			for (int k = 0; k < MAXM; k++)
				for (int a = 0; a < MAXM; a++)
					T[i][j][k] = (T[i][j][k] + F[a][i] * F[a][j] * F[a][k]) % MOD;

	for (int a = 0; a < MAXM; a++)
		for (int b = 0; b < MAXM; b++)
			for (int c = 0; c < MAXM; c++)
				for (int d = 0; d < MAXM; d++)
					ans = (ans + T[a][b][c] * T[a][b][d] % MOD * T[a][c][d] % MOD * T[b][c][d]) % MOD;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	while (t--) {
		string s;
		cin >> s;

		vec[s.size()].push_back(s);
		reverse(all(s));
		vec[s.size()].push_back(s);
	}

	for (int i = 3; i <= 10; i++)
		solve(i);

	cout << ans << endl;
	return 0;
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 734 ms 211576 KB Output is correct
2 Correct 747 ms 211612 KB Output is correct
3 Correct 750 ms 211524 KB Output is correct
4 Correct 739 ms 211644 KB Output is correct
5 Correct 745 ms 211644 KB Output is correct
6 Correct 759 ms 211784 KB Output is correct
7 Correct 744 ms 211600 KB Output is correct
8 Correct 742 ms 211572 KB Output is correct
9 Correct 744 ms 211668 KB Output is correct
10 Correct 743 ms 211708 KB Output is correct
11 Correct 739 ms 211576 KB Output is correct
12 Correct 739 ms 211636 KB Output is correct
13 Correct 747 ms 211684 KB Output is correct
14 Correct 741 ms 211524 KB Output is correct
15 Correct 751 ms 211616 KB Output is correct
16 Correct 742 ms 211692 KB Output is correct
17 Correct 748 ms 211612 KB Output is correct
18 Correct 739 ms 211500 KB Output is correct
19 Correct 742 ms 211580 KB Output is correct
20 Correct 747 ms 211600 KB Output is correct
21 Correct 749 ms 211640 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 734 ms 211576 KB Output is correct
2 Correct 747 ms 211612 KB Output is correct
3 Correct 750 ms 211524 KB Output is correct
4 Correct 739 ms 211644 KB Output is correct
5 Correct 745 ms 211644 KB Output is correct
6 Correct 759 ms 211784 KB Output is correct
7 Correct 744 ms 211600 KB Output is correct
8 Correct 742 ms 211572 KB Output is correct
9 Correct 744 ms 211668 KB Output is correct
10 Correct 743 ms 211708 KB Output is correct
11 Correct 739 ms 211576 KB Output is correct
12 Correct 739 ms 211636 KB Output is correct
13 Correct 747 ms 211684 KB Output is correct
14 Correct 741 ms 211524 KB Output is correct
15 Correct 751 ms 211616 KB Output is correct
16 Correct 742 ms 211692 KB Output is correct
17 Correct 748 ms 211612 KB Output is correct
18 Correct 739 ms 211500 KB Output is correct
19 Correct 742 ms 211580 KB Output is correct
20 Correct 747 ms 211600 KB Output is correct
21 Correct 749 ms 211640 KB Output is correct
22 Correct 744 ms 211320 KB Output is correct
23 Correct 737 ms 211384 KB Output is correct
24 Correct 742 ms 211568 KB Output is correct
25 Correct 740 ms 211536 KB Output is correct
26 Correct 740 ms 211516 KB Output is correct
27 Correct 736 ms 211728 KB Output is correct
28 Correct 743 ms 211488 KB Output is correct
29 Correct 744 ms 211408 KB Output is correct
30 Correct 753 ms 211352 KB Output is correct
31 Correct 736 ms 211392 KB Output is correct
32 Correct 739 ms 211276 KB Output is correct
33 Correct 732 ms 211380 KB Output is correct
34 Correct 743 ms 211536 KB Output is correct
35 Correct 738 ms 211540 KB Output is correct
36 Correct 743 ms 211480 KB Output is correct
37 Correct 847 ms 211484 KB Output is correct
38 Correct 746 ms 211528 KB Output is correct
39 Correct 744 ms 211568 KB Output is correct
40 Correct 743 ms 211544 KB Output is correct
41 Correct 742 ms 211544 KB Output is correct
42 Correct 733 ms 211364 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 734 ms 211576 KB Output is correct
2 Correct 747 ms 211612 KB Output is correct
3 Correct 750 ms 211524 KB Output is correct
4 Correct 739 ms 211644 KB Output is correct
5 Correct 745 ms 211644 KB Output is correct
6 Correct 759 ms 211784 KB Output is correct
7 Correct 744 ms 211600 KB Output is correct
8 Correct 742 ms 211572 KB Output is correct
9 Correct 744 ms 211668 KB Output is correct
10 Correct 743 ms 211708 KB Output is correct
11 Correct 739 ms 211576 KB Output is correct
12 Correct 739 ms 211636 KB Output is correct
13 Correct 747 ms 211684 KB Output is correct
14 Correct 741 ms 211524 KB Output is correct
15 Correct 751 ms 211616 KB Output is correct
16 Correct 742 ms 211692 KB Output is correct
17 Correct 748 ms 211612 KB Output is correct
18 Correct 739 ms 211500 KB Output is correct
19 Correct 742 ms 211580 KB Output is correct
20 Correct 747 ms 211600 KB Output is correct
21 Correct 749 ms 211640 KB Output is correct
22 Correct 744 ms 211320 KB Output is correct
23 Correct 737 ms 211384 KB Output is correct
24 Correct 742 ms 211568 KB Output is correct
25 Correct 740 ms 211536 KB Output is correct
26 Correct 740 ms 211516 KB Output is correct
27 Correct 736 ms 211728 KB Output is correct
28 Correct 743 ms 211488 KB Output is correct
29 Correct 744 ms 211408 KB Output is correct
30 Correct 753 ms 211352 KB Output is correct
31 Correct 736 ms 211392 KB Output is correct
32 Correct 739 ms 211276 KB Output is correct
33 Correct 732 ms 211380 KB Output is correct
34 Correct 743 ms 211536 KB Output is correct
35 Correct 738 ms 211540 KB Output is correct
36 Correct 743 ms 211480 KB Output is correct
37 Correct 847 ms 211484 KB Output is correct
38 Correct 746 ms 211528 KB Output is correct
39 Correct 744 ms 211568 KB Output is correct
40 Correct 743 ms 211544 KB Output is correct
41 Correct 742 ms 211544 KB Output is correct
42 Correct 733 ms 211364 KB Output is correct
43 Correct 763 ms 211284 KB Output is correct
44 Correct 765 ms 212144 KB Output is correct
45 Correct 762 ms 212132 KB Output is correct
46 Correct 763 ms 212136 KB Output is correct
47 Correct 772 ms 212132 KB Output is correct
48 Correct 765 ms 212516 KB Output is correct
49 Correct 767 ms 212512 KB Output is correct
50 Correct 752 ms 212520 KB Output is correct
51 Correct 759 ms 212380 KB Output is correct
52 Correct 764 ms 212096 KB Output is correct
53 Correct 762 ms 212096 KB Output is correct
54 Correct 773 ms 212480 KB Output is correct
55 Correct 783 ms 212616 KB Output is correct
56 Correct 763 ms 212140 KB Output is correct
57 Correct 762 ms 212484 KB Output is correct
58 Correct 758 ms 212544 KB Output is correct
59 Correct 757 ms 212356 KB Output is correct
60 Correct 752 ms 212476 KB Output is correct
61 Correct 760 ms 212160 KB Output is correct
62 Correct 762 ms 212352 KB Output is correct
63 Correct 758 ms 212380 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 734 ms 211576 KB Output is correct
2 Correct 747 ms 211612 KB Output is correct
3 Correct 750 ms 211524 KB Output is correct
4 Correct 739 ms 211644 KB Output is correct
5 Correct 745 ms 211644 KB Output is correct
6 Correct 759 ms 211784 KB Output is correct
7 Correct 744 ms 211600 KB Output is correct
8 Correct 742 ms 211572 KB Output is correct
9 Correct 744 ms 211668 KB Output is correct
10 Correct 743 ms 211708 KB Output is correct
11 Correct 739 ms 211576 KB Output is correct
12 Correct 739 ms 211636 KB Output is correct
13 Correct 747 ms 211684 KB Output is correct
14 Correct 741 ms 211524 KB Output is correct
15 Correct 751 ms 211616 KB Output is correct
16 Correct 742 ms 211692 KB Output is correct
17 Correct 748 ms 211612 KB Output is correct
18 Correct 739 ms 211500 KB Output is correct
19 Correct 742 ms 211580 KB Output is correct
20 Correct 747 ms 211600 KB Output is correct
21 Correct 749 ms 211640 KB Output is correct
22 Correct 744 ms 211320 KB Output is correct
23 Correct 737 ms 211384 KB Output is correct
24 Correct 742 ms 211568 KB Output is correct
25 Correct 740 ms 211536 KB Output is correct
26 Correct 740 ms 211516 KB Output is correct
27 Correct 736 ms 211728 KB Output is correct
28 Correct 743 ms 211488 KB Output is correct
29 Correct 744 ms 211408 KB Output is correct
30 Correct 753 ms 211352 KB Output is correct
31 Correct 736 ms 211392 KB Output is correct
32 Correct 739 ms 211276 KB Output is correct
33 Correct 732 ms 211380 KB Output is correct
34 Correct 743 ms 211536 KB Output is correct
35 Correct 738 ms 211540 KB Output is correct
36 Correct 743 ms 211480 KB Output is correct
37 Correct 847 ms 211484 KB Output is correct
38 Correct 746 ms 211528 KB Output is correct
39 Correct 744 ms 211568 KB Output is correct
40 Correct 743 ms 211544 KB Output is correct
41 Correct 742 ms 211544 KB Output is correct
42 Correct 733 ms 211364 KB Output is correct
43 Correct 763 ms 211284 KB Output is correct
44 Correct 765 ms 212144 KB Output is correct
45 Correct 762 ms 212132 KB Output is correct
46 Correct 763 ms 212136 KB Output is correct
47 Correct 772 ms 212132 KB Output is correct
48 Correct 765 ms 212516 KB Output is correct
49 Correct 767 ms 212512 KB Output is correct
50 Correct 752 ms 212520 KB Output is correct
51 Correct 759 ms 212380 KB Output is correct
52 Correct 764 ms 212096 KB Output is correct
53 Correct 762 ms 212096 KB Output is correct
54 Correct 773 ms 212480 KB Output is correct
55 Correct 783 ms 212616 KB Output is correct
56 Correct 763 ms 212140 KB Output is correct
57 Correct 762 ms 212484 KB Output is correct
58 Correct 758 ms 212544 KB Output is correct
59 Correct 757 ms 212356 KB Output is correct
60 Correct 752 ms 212476 KB Output is correct
61 Correct 760 ms 212160 KB Output is correct
62 Correct 762 ms 212352 KB Output is correct
63 Correct 758 ms 212380 KB Output is correct
64 Runtime error 917 ms 429600 KB Execution killed with signal 11
65 Halted 0 ms 0 KB -