oj.uz

Submission #674489

# Submission time Handle Problem Language Result Execution time Memory
674489 2022-12-24T14:21:32 Z Sohsoh84 Cubeword (CEOI19_cubeword) C++17
50 / 100
 258 ms 208144 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;
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 170 ms 108788 KB Output is correct
2 Correct 174 ms 109736 KB Output is correct
3 Correct 169 ms 109640 KB Output is correct
4 Correct 170 ms 109696 KB Output is correct
5 Correct 171 ms 109752 KB Output is correct
6 Correct 176 ms 109900 KB Output is correct
7 Correct 169 ms 109720 KB Output is correct
8 Correct 173 ms 109668 KB Output is correct
9 Correct 171 ms 109652 KB Output is correct
10 Correct 173 ms 109716 KB Output is correct
11 Correct 185 ms 109940 KB Output is correct
12 Correct 172 ms 109656 KB Output is correct
13 Correct 171 ms 109760 KB Output is correct
14 Correct 169 ms 109612 KB Output is correct
15 Correct 174 ms 109712 KB Output is correct
16 Correct 170 ms 109748 KB Output is correct
17 Correct 174 ms 109728 KB Output is correct
18 Correct 178 ms 109500 KB Output is correct
19 Correct 171 ms 109804 KB Output is correct
20 Correct 172 ms 109600 KB Output is correct
21 Correct 173 ms 109748 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 108788 KB Output is correct
2 Correct 174 ms 109736 KB Output is correct
3 Correct 169 ms 109640 KB Output is correct
4 Correct 170 ms 109696 KB Output is correct
5 Correct 171 ms 109752 KB Output is correct
6 Correct 176 ms 109900 KB Output is correct
7 Correct 169 ms 109720 KB Output is correct
8 Correct 173 ms 109668 KB Output is correct
9 Correct 171 ms 109652 KB Output is correct
10 Correct 173 ms 109716 KB Output is correct
11 Correct 185 ms 109940 KB Output is correct
12 Correct 172 ms 109656 KB Output is correct
13 Correct 171 ms 109760 KB Output is correct
14 Correct 169 ms 109612 KB Output is correct
15 Correct 174 ms 109712 KB Output is correct
16 Correct 170 ms 109748 KB Output is correct
17 Correct 174 ms 109728 KB Output is correct
18 Correct 178 ms 109500 KB Output is correct
19 Correct 171 ms 109804 KB Output is correct
20 Correct 172 ms 109600 KB Output is correct
21 Correct 173 ms 109748 KB Output is correct
22 Correct 174 ms 109336 KB Output is correct
23 Correct 169 ms 109416 KB Output is correct
24 Correct 167 ms 109496 KB Output is correct
25 Correct 173 ms 109608 KB Output is correct
26 Correct 171 ms 109444 KB Output is correct
27 Correct 187 ms 109592 KB Output is correct
28 Correct 170 ms 109420 KB Output is correct
29 Correct 172 ms 109432 KB Output is correct
30 Correct 173 ms 109436 KB Output is correct
31 Correct 170 ms 109312 KB Output is correct
32 Correct 171 ms 109348 KB Output is correct
33 Correct 170 ms 109348 KB Output is correct
34 Correct 172 ms 109408 KB Output is correct
35 Correct 168 ms 109588 KB Output is correct
36 Correct 175 ms 109584 KB Output is correct
37 Correct 168 ms 109528 KB Output is correct
38 Correct 169 ms 109560 KB Output is correct
39 Correct 166 ms 109476 KB Output is correct
40 Correct 168 ms 109548 KB Output is correct
41 Correct 169 ms 109528 KB Output is correct
42 Correct 169 ms 109364 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 108788 KB Output is correct
2 Correct 174 ms 109736 KB Output is correct
3 Correct 169 ms 109640 KB Output is correct
4 Correct 170 ms 109696 KB Output is correct
5 Correct 171 ms 109752 KB Output is correct
6 Correct 176 ms 109900 KB Output is correct
7 Correct 169 ms 109720 KB Output is correct
8 Correct 173 ms 109668 KB Output is correct
9 Correct 171 ms 109652 KB Output is correct
10 Correct 173 ms 109716 KB Output is correct
11 Correct 185 ms 109940 KB Output is correct
12 Correct 172 ms 109656 KB Output is correct
13 Correct 171 ms 109760 KB Output is correct
14 Correct 169 ms 109612 KB Output is correct
15 Correct 174 ms 109712 KB Output is correct
16 Correct 170 ms 109748 KB Output is correct
17 Correct 174 ms 109728 KB Output is correct
18 Correct 178 ms 109500 KB Output is correct
19 Correct 171 ms 109804 KB Output is correct
20 Correct 172 ms 109600 KB Output is correct
21 Correct 173 ms 109748 KB Output is correct
22 Correct 174 ms 109336 KB Output is correct
23 Correct 169 ms 109416 KB Output is correct
24 Correct 167 ms 109496 KB Output is correct
25 Correct 173 ms 109608 KB Output is correct
26 Correct 171 ms 109444 KB Output is correct
27 Correct 187 ms 109592 KB Output is correct
28 Correct 170 ms 109420 KB Output is correct
29 Correct 172 ms 109432 KB Output is correct
30 Correct 173 ms 109436 KB Output is correct
31 Correct 170 ms 109312 KB Output is correct
32 Correct 171 ms 109348 KB Output is correct
33 Correct 170 ms 109348 KB Output is correct
34 Correct 172 ms 109408 KB Output is correct
35 Correct 168 ms 109588 KB Output is correct
36 Correct 175 ms 109584 KB Output is correct
37 Correct 168 ms 109528 KB Output is correct
38 Correct 169 ms 109560 KB Output is correct
39 Correct 166 ms 109476 KB Output is correct
40 Correct 168 ms 109548 KB Output is correct
41 Correct 169 ms 109528 KB Output is correct
42 Correct 169 ms 109364 KB Output is correct
43 Runtime error 258 ms 208144 KB Execution killed with signal 11
44 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 108788 KB Output is correct
2 Correct 174 ms 109736 KB Output is correct
3 Correct 169 ms 109640 KB Output is correct
4 Correct 170 ms 109696 KB Output is correct
5 Correct 171 ms 109752 KB Output is correct
6 Correct 176 ms 109900 KB Output is correct
7 Correct 169 ms 109720 KB Output is correct
8 Correct 173 ms 109668 KB Output is correct
9 Correct 171 ms 109652 KB Output is correct
10 Correct 173 ms 109716 KB Output is correct
11 Correct 185 ms 109940 KB Output is correct
12 Correct 172 ms 109656 KB Output is correct
13 Correct 171 ms 109760 KB Output is correct
14 Correct 169 ms 109612 KB Output is correct
15 Correct 174 ms 109712 KB Output is correct
16 Correct 170 ms 109748 KB Output is correct
17 Correct 174 ms 109728 KB Output is correct
18 Correct 178 ms 109500 KB Output is correct
19 Correct 171 ms 109804 KB Output is correct
20 Correct 172 ms 109600 KB Output is correct
21 Correct 173 ms 109748 KB Output is correct
22 Correct 174 ms 109336 KB Output is correct
23 Correct 169 ms 109416 KB Output is correct
24 Correct 167 ms 109496 KB Output is correct
25 Correct 173 ms 109608 KB Output is correct
26 Correct 171 ms 109444 KB Output is correct
27 Correct 187 ms 109592 KB Output is correct
28 Correct 170 ms 109420 KB Output is correct
29 Correct 172 ms 109432 KB Output is correct
30 Correct 173 ms 109436 KB Output is correct
31 Correct 170 ms 109312 KB Output is correct
32 Correct 171 ms 109348 KB Output is correct
33 Correct 170 ms 109348 KB Output is correct
34 Correct 172 ms 109408 KB Output is correct
35 Correct 168 ms 109588 KB Output is correct
36 Correct 175 ms 109584 KB Output is correct
37 Correct 168 ms 109528 KB Output is correct
38 Correct 169 ms 109560 KB Output is correct
39 Correct 166 ms 109476 KB Output is correct
40 Correct 168 ms 109548 KB Output is correct
41 Correct 169 ms 109528 KB Output is correct
42 Correct 169 ms 109364 KB Output is correct
43 Runtime error 258 ms 208144 KB Execution killed with signal 11
44 Halted 0 ms 0 KB -