Submission #779530

#	Time	Username	Problem	Language	Result	Execution time	Memory
779530		ThegeekKnight16	Cubeword (CEOI19_cubeword)	C++17	100 / 100	956 ms	35468 KiB

cubeword

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 998244353;
const int MAXN = 72;
const int MAXT = 11;
//Freq of two ends of and edge
int freq[MAXT][MAXN][MAXN];
//Freq of the meeting of three edges
int freq3[MAXT][MAXN][MAXN][MAXN];
int letters[MAXT];
map<char, int> comp[MAXT];
set<string> palav[MAXT];
int resp = 0;
 
inline int add(int a, int b) {return (a + b) % MOD;}
inline int mult(int a, int b) {return (a * b) % MOD;}
 
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        string s;
        cin >> s;
        palav[s.size()].insert(s);
        reverse(s.begin(), s.end());
        palav[s.size()].insert(s);
    }
 
    for (int i = 3; i < MAXT; i++)
    {
        for (auto &s : palav[i])
        {
            char b = s[0], f = s.back();
            if (comp[i][b] == 0) comp[i][b] = ++letters[i];
            if (comp[i][f] == 0) comp[i][f] = ++letters[i];
            freq[i][comp[i][b]][comp[i][f]]++;
        }
    }
 
    for (int t = 3; t < MAXT; t++)
    {
        for (int i = 1; i <= letters[t]; i++)
        {
            for (int j = i; j <= letters[t]; j++)
            {
                for (int k = j; k <= letters[t]; k++)
                {
                    for (int x = 1; x <= letters[t]; x++)
                    {
                        freq3[t][i][j][k] = freq3[t][i][k][j] = freq3[t][j][i][k] = freq3[t][j][k][i] = freq3[t][k][i][j] = freq3[t][k][j][i] = add(freq3[t][i][j][k], mult(freq[t][i][x], mult(freq[t][j][x], freq[t][k][x])));
                    }
                }
            }
        }
    }
 
    for (int t = 3; t < MAXT; t++)
    {
        for (int i = 1; i <= letters[t]; i++)
        {
            for (int j = 1; j <= letters[t]; j++)
            {
                for (int k = 1; k <= letters[t]; k++)
                {
                    int ansX = freq3[t][i][j][k];
                    if (ansX == 0) continue;
                    for (int l = 1; l <= letters[t]; l++)
                    {
                        int ans = ansX;
                        ans = mult(ans, freq3[t][i][j][l]);
                        ans = mult(ans, freq3[t][i][k][l]);
                        ans = mult(ans, freq3[t][j][k][l]);
                        resp = add(resp, ans);
                    }
                }
            }
        }
    }
 
    cout << resp << '\n';
}

• Subtask 1: 21 / 21
• Subtask 2: 29 / 29
• Subtask 3: 34 / 34
• Subtask 4: 16 / 16