oj.uz

Submission #674491

# Submission time Handle Problem Language Result Execution time Memory
674491 2022-12-24T14:23:54 Z Sohsoh84 Cubeword (CEOI19_cubeword) C++17
0 / 100
 1100 ms 251436 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 + 10;
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
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1210 ms 251436 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1210 ms 251436 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1210 ms 251436 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1210 ms 251436 KB Time limit exceeded
2 Halted 0 ms 0 KB -