oj.uz

Submission #314904

# Submission time Handle Problem Language Result Execution time Memory
314904 2020-10-21T15:36:05 Z shivensinha4 Cubeword (CEOI19_cubeword) C++17
21 / 100
 1100 ms 21656 KB 
#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<unordered_set<string>> raw(11);
	for_(i, 0, n) {
		string s; cin >> s;
		if (raw[s.size()].count(s)) 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 197 ms 20168 KB Output is correct
2 Correct 191 ms 20928 KB Output is correct
3 Correct 193 ms 21056 KB Output is correct
4 Correct 192 ms 21112 KB Output is correct
5 Correct 196 ms 21060 KB Output is correct
6 Correct 196 ms 20932 KB Output is correct
7 Correct 191 ms 21112 KB Output is correct
8 Correct 200 ms 20932 KB Output is correct
9 Correct 192 ms 21060 KB Output is correct
10 Correct 189 ms 21060 KB Output is correct
11 Correct 188 ms 20932 KB Output is correct
12 Correct 202 ms 20932 KB Output is correct
13 Correct 194 ms 21060 KB Output is correct
14 Correct 194 ms 21128 KB Output is correct
15 Correct 194 ms 21060 KB Output is correct
16 Correct 192 ms 20932 KB Output is correct
17 Correct 204 ms 20932 KB Output is correct
18 Correct 190 ms 20944 KB Output is correct
19 Correct 194 ms 20932 KB Output is correct
20 Correct 197 ms 21060 KB Output is correct
21 Correct 190 ms 20932 KB Output is correct

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 20168 KB Output is correct
2 Correct 191 ms 20928 KB Output is correct
3 Correct 193 ms 21056 KB Output is correct
4 Correct 192 ms 21112 KB Output is correct
5 Correct 196 ms 21060 KB Output is correct
6 Correct 196 ms 20932 KB Output is correct
7 Correct 191 ms 21112 KB Output is correct
8 Correct 200 ms 20932 KB Output is correct
9 Correct 192 ms 21060 KB Output is correct
10 Correct 189 ms 21060 KB Output is correct
11 Correct 188 ms 20932 KB Output is correct
12 Correct 202 ms 20932 KB Output is correct
13 Correct 194 ms 21060 KB Output is correct
14 Correct 194 ms 21128 KB Output is correct
15 Correct 194 ms 21060 KB Output is correct
16 Correct 192 ms 20932 KB Output is correct
17 Correct 204 ms 20932 KB Output is correct
18 Correct 190 ms 20944 KB Output is correct
19 Correct 194 ms 20932 KB Output is correct
20 Correct 197 ms 21060 KB Output is correct
21 Correct 190 ms 20932 KB Output is correct
22 Execution timed out 1181 ms 21656 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 20168 KB Output is correct
2 Correct 191 ms 20928 KB Output is correct
3 Correct 193 ms 21056 KB Output is correct
4 Correct 192 ms 21112 KB Output is correct
5 Correct 196 ms 21060 KB Output is correct
6 Correct 196 ms 20932 KB Output is correct
7 Correct 191 ms 21112 KB Output is correct
8 Correct 200 ms 20932 KB Output is correct
9 Correct 192 ms 21060 KB Output is correct
10 Correct 189 ms 21060 KB Output is correct
11 Correct 188 ms 20932 KB Output is correct
12 Correct 202 ms 20932 KB Output is correct
13 Correct 194 ms 21060 KB Output is correct
14 Correct 194 ms 21128 KB Output is correct
15 Correct 194 ms 21060 KB Output is correct
16 Correct 192 ms 20932 KB Output is correct
17 Correct 204 ms 20932 KB Output is correct
18 Correct 190 ms 20944 KB Output is correct
19 Correct 194 ms 20932 KB Output is correct
20 Correct 197 ms 21060 KB Output is correct
21 Correct 190 ms 20932 KB Output is correct
22 Execution timed out 1181 ms 21656 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 20168 KB Output is correct
2 Correct 191 ms 20928 KB Output is correct
3 Correct 193 ms 21056 KB Output is correct
4 Correct 192 ms 21112 KB Output is correct
5 Correct 196 ms 21060 KB Output is correct
6 Correct 196 ms 20932 KB Output is correct
7 Correct 191 ms 21112 KB Output is correct
8 Correct 200 ms 20932 KB Output is correct
9 Correct 192 ms 21060 KB Output is correct
10 Correct 189 ms 21060 KB Output is correct
11 Correct 188 ms 20932 KB Output is correct
12 Correct 202 ms 20932 KB Output is correct
13 Correct 194 ms 21060 KB Output is correct
14 Correct 194 ms 21128 KB Output is correct
15 Correct 194 ms 21060 KB Output is correct
16 Correct 192 ms 20932 KB Output is correct
17 Correct 204 ms 20932 KB Output is correct
18 Correct 190 ms 20944 KB Output is correct
19 Correct 194 ms 20932 KB Output is correct
20 Correct 197 ms 21060 KB Output is correct
21 Correct 190 ms 20932 KB Output is correct
22 Execution timed out 1181 ms 21656 KB Time limit exceeded
23 Halted 0 ms 0 KB -