oj.uz

Submission #546565

# Submission time Handle Problem Language Result Execution time Memory
546565 2022-04-07T20:23:00 Z LucaDantas Cubeword (CEOI19_cubeword) C++17
0 / 100
 1100 ms 15760 KB 
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 16, mod = 998244353; // subtasks 1-2

int ans;

int edge[11][maxn][maxn];

int value_triad[11][maxn][maxn][maxn];

int id(char c) { return c-'a'; } // subtaks 1-2

set<string> mark;

void add(int& a, int b) { a += b; if(a >= mod) a -= mod; }

int main() {
    int n; cin >> n;
    string s;
    for(int i = 0; i < n; i++) {
        cin >> s;
        for(int rep = 0; rep < 2; rep++, reverse(s.begin(), s.end())) if(!mark.count(s)) {
            edge[s.size()][id(s[0])][id(s.back())]++;
            mark.insert(s);
        }
    }

    vector<array<int,3>> triad;
    for(int a = 0; a < maxn; a++)
        for(int b = 0; b < maxn; b++)
            for(int c = 0; c < maxn; c++)
                triad.push_back({a, b, c});


    for(int sz = 3; sz <= 10; sz++) {
        for(auto [a, b, c] : triad)
            for(int x = 0; x < maxn; x++)
                add(value_triad[sz][a][b][c], 1ll * edge[sz][x][a] * edge[sz][x][b] * edge[sz][x][c] % mod);

        for(auto [a1, b1, c1] : triad) for(auto [a2, b2, c2] : triad) {
            long long aq = 1ll * value_triad[sz][a1][b1][c1] * value_triad[sz][a2][b2][c2] % mod;
            aq *= 1ll * edge[sz][a1][b2] * edge[sz][a1][c2] % mod; aq %= mod;
            aq *= 1ll * edge[sz][b1][a2] * edge[sz][b1][c2] % mod; aq %= mod;
            aq *= 1ll * edge[sz][c1][a2] * edge[sz][c1][b2] % mod; aq %= mod;
            
            add(ans, aq);
        }
    }

    printf("%d\n", ans);
}

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1185 ms 15760 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 1185 ms 15760 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 1185 ms 15760 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 1185 ms 15760 KB Time limit exceeded
2 Halted 0 ms 0 KB -