oj.uz

Submission #314908

# Submission time Handle Problem Language Result Execution time Memory
314908 2020-10-21T15:37:54 Z shivensinha4 Cubeword (CEOI19_cubeword) C++17
21 / 100
 1100 ms 33268 KB 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#include <bits/stdc++.h> 
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
//#define endl '\n'

const int MXV = 16;
const ll mod = 998244353;
ll trans[MXV+1][MXV+1], ct[MXV+1][MXV+1][MXV+1][MXV+1], cts[MXV+1][MXV+1][MXV+1][MXV+1];
bool curr[MXV+1];

int getChar(char a) {
	//cout << a << " " << (a >= 'a' ? (a-'a') : (16+a-'A')) << endl;
	int v = a >= 'a' ? (a-'a') : (16+a-'A');
	assert(v <= MXV);
	return v;
}

ll mul(vector<ll> nums) {
	ll ans = nums[0];
	for_(i, 1, nums.size()) ans = (ans * nums[i]) % mod;
	return ans;
}

int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n; cin >> n;
	vector<vector<vi>> words(11);
	vector<gp_hash_table<string, null_type>> raw(11);
	for_(i, 0, n) {
		string s; cin >> s;
		if (raw[s.size()].find(s) != raw[s.size()].end()) continue;
		int a = getChar(s[0]), b = getChar(s.back()), c;
		string temp = s;
		reverse(temp.begin(), temp.end());
		c = temp == s;
		words[s.size()].push_back({a, b, c});
		raw[s.size()].insert(s);
		if (!c) raw[s.size()].insert(temp);
	}
	
	ll ans = 0;
	for_(l, 3, 11) {
		if (!words[l].size()) continue;
		//cout << l << "-------" << endl;
		memset(trans, 0, sizeof(trans)); memset(ct, 0, sizeof(ct)); memset(ct, 0, sizeof(cts)); memset(curr, false, sizeof(curr));
		vi used;
		ll v;
		for (auto i: words[l]) {
			trans[i[0]][i[1]] += 1;
			if (!curr[i[0]]) used.push_back(i[0]);
			if (i[0] != i[1] and !curr[i[1]]) used.push_back(i[1]);
			curr[i[0]] = curr[i[1]] = true;
			if (!i[2]) trans[i[1]][i[0]] += 1;
		}
		for (int a: used) for (int b: used) for (int c: used) for (int d: used) {
			cts[a][b][c][d] = mul({trans[a][b], trans[b][c], trans[c][d], trans[d][a]});
			v = cts[a][b][c][d];
			if (!v) continue;
			
			for (int cc: used) for (int dd: used) {
				ct[a][b][cc][dd] += mul({v, trans[c][cc], trans[d][dd]});
				if (ct[a][b][cc][dd] >= mod) ct[a][b][cc][dd] -= mod;
			}
		}
		for (int a: used) for (int b: used) for (int c: used) for (int d: used) {
			if (!cts[a][b][c][d]) continue;
			for (int aa: used) for (int bb: used) {
				ans += mul({cts[a][b][c][d], ct[aa][bb][c][d], trans[a][aa], trans[b][bb]});
				if (ans >= mod) ans -= mod;
			}
		}
	}
	
	cout << ans << endl;
	

	return 0;
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 32984 KB Output is correct
2 Correct 151 ms 32596 KB Output is correct
3 Correct 157 ms 32620 KB Output is correct
4 Correct 150 ms 32520 KB Output is correct
5 Correct 153 ms 33268 KB Output is correct
6 Correct 152 ms 32984 KB Output is correct
7 Correct 152 ms 32968 KB Output is correct
8 Correct 156 ms 32544 KB Output is correct
9 Correct 153 ms 32940 KB Output is correct
10 Correct 170 ms 32928 KB Output is correct
11 Correct 154 ms 33012 KB Output is correct
12 Correct 156 ms 32984 KB Output is correct
13 Correct 153 ms 32904 KB Output is correct
14 Correct 150 ms 32600 KB Output is correct
15 Correct 155 ms 32988 KB Output is correct
16 Correct 150 ms 32980 KB Output is correct
17 Correct 158 ms 33096 KB Output is correct
18 Correct 150 ms 32984 KB Output is correct
19 Correct 159 ms 32976 KB Output is correct
20 Correct 150 ms 32976 KB Output is correct
21 Correct 151 ms 32540 KB Output is correct

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 32984 KB Output is correct
2 Correct 151 ms 32596 KB Output is correct
3 Correct 157 ms 32620 KB Output is correct
4 Correct 150 ms 32520 KB Output is correct
5 Correct 153 ms 33268 KB Output is correct
6 Correct 152 ms 32984 KB Output is correct
7 Correct 152 ms 32968 KB Output is correct
8 Correct 156 ms 32544 KB Output is correct
9 Correct 153 ms 32940 KB Output is correct
10 Correct 170 ms 32928 KB Output is correct
11 Correct 154 ms 33012 KB Output is correct
12 Correct 156 ms 32984 KB Output is correct
13 Correct 153 ms 32904 KB Output is correct
14 Correct 150 ms 32600 KB Output is correct
15 Correct 155 ms 32988 KB Output is correct
16 Correct 150 ms 32980 KB Output is correct
17 Correct 158 ms 33096 KB Output is correct
18 Correct 150 ms 32984 KB Output is correct
19 Correct 159 ms 32976 KB Output is correct
20 Correct 150 ms 32976 KB Output is correct
21 Correct 151 ms 32540 KB Output is correct
22 Execution timed out 1187 ms 25496 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 32984 KB Output is correct
2 Correct 151 ms 32596 KB Output is correct
3 Correct 157 ms 32620 KB Output is correct
4 Correct 150 ms 32520 KB Output is correct
5 Correct 153 ms 33268 KB Output is correct
6 Correct 152 ms 32984 KB Output is correct
7 Correct 152 ms 32968 KB Output is correct
8 Correct 156 ms 32544 KB Output is correct
9 Correct 153 ms 32940 KB Output is correct
10 Correct 170 ms 32928 KB Output is correct
11 Correct 154 ms 33012 KB Output is correct
12 Correct 156 ms 32984 KB Output is correct
13 Correct 153 ms 32904 KB Output is correct
14 Correct 150 ms 32600 KB Output is correct
15 Correct 155 ms 32988 KB Output is correct
16 Correct 150 ms 32980 KB Output is correct
17 Correct 158 ms 33096 KB Output is correct
18 Correct 150 ms 32984 KB Output is correct
19 Correct 159 ms 32976 KB Output is correct
20 Correct 150 ms 32976 KB Output is correct
21 Correct 151 ms 32540 KB Output is correct
22 Execution timed out 1187 ms 25496 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 32984 KB Output is correct
2 Correct 151 ms 32596 KB Output is correct
3 Correct 157 ms 32620 KB Output is correct
4 Correct 150 ms 32520 KB Output is correct
5 Correct 153 ms 33268 KB Output is correct
6 Correct 152 ms 32984 KB Output is correct
7 Correct 152 ms 32968 KB Output is correct
8 Correct 156 ms 32544 KB Output is correct
9 Correct 153 ms 32940 KB Output is correct
10 Correct 170 ms 32928 KB Output is correct
11 Correct 154 ms 33012 KB Output is correct
12 Correct 156 ms 32984 KB Output is correct
13 Correct 153 ms 32904 KB Output is correct
14 Correct 150 ms 32600 KB Output is correct
15 Correct 155 ms 32988 KB Output is correct
16 Correct 150 ms 32980 KB Output is correct
17 Correct 158 ms 33096 KB Output is correct
18 Correct 150 ms 32984 KB Output is correct
19 Correct 159 ms 32976 KB Output is correct
20 Correct 150 ms 32976 KB Output is correct
21 Correct 151 ms 32540 KB Output is correct
22 Execution timed out 1187 ms 25496 KB Time limit exceeded
23 Halted 0 ms 0 KB -