oj.uz

Submission #445663

# Submission time Handle Problem Language Result Execution time Memory
445663 2021-07-19T08:26:18 Z Haruto810198 Cubeword (CEOI19_cubeword) C++17
0 / 100
 1100 ms 7564 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i,l,r,d) for(int i=(l);i<=(r);i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int,int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = 2147483647;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 65;
int SZ = 16; /// Subtask 2

int n;
map<char, int> char_id;

vector<string> strings[11];

set<string> edges[MAX][MAX];

int edge_cnt[MAX][MAX];
int half_cnt[MAX][MAX][MAX];

int res;

signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    /// a~p -> 0~15
    for(char i='a'; i<='p'; i++){
        char_id[i] = i - 'a';
    }

    /// A~P -> 16~31
    for(char i='A'; i<='P'; i++){
        char_id[i] = i - 'A' + 16;
    }

    /// q~z -> 32~41
    for(char i='q'; i<='z'; i++){
        char_id[i] = i - 'a' + 16;
    }

    /// Q~Z -> 42~51
    for(char i='Q'; i<='Z'; i++){
        char_id[i] = i - 'A' + 26;
    }

    /// 0~9 -> 52~61
    for(char i='0'; i<='9'; i++){
        char_id[i] = i - '0' + 52;
    }

    cin>>n;

    FOR(i, 1, n, 1){
        string str;
        cin>>str;
        strings[szof(str)].pb(str);
    }

    /// L = len. of strings
    FOR(L, 3, 10, 1){

        FOR(i, 0, SZ-1, 1){
            FOR(j, 0, SZ-1, 1){
                edges[i][j].clear();
            }
        }

        for(string S : strings[L]){
            int u = char_id[ S[0] ];
            int v = char_id[ S[L-1] ];
            edges[u][v].insert(S);
            reverse(S.begin(), S.end());
            edges[v][u].insert(S);
        }

        FOR(i, 0, SZ-1, 1){
            FOR(j, 0, SZ-1, 1){
                edge_cnt[i][j] = szof(edges[i][j]);
            }
        }

        /// one half

        FOR(i, 0, SZ-1, 1){
            FOR(j, 0, SZ-1, 1){
                FOR(k, 0, SZ-1, 1){
                    half_cnt[i][j][k] = 0;
                }
            }
        }

        FOR(A, 0, SZ-1, 1){
            FOR(B, 0, SZ-1, 1){
                FOR(D, 0, SZ-1, 1){
                    FOR(E, 0, SZ-1, 1){
                        half_cnt[B][D][E] += edge_cnt[A][B] * edge_cnt[A][D] * edge_cnt[A][E];
                        half_cnt[B][D][E] %= mod;
                    }
                }
            }
        }

        /// another half

        FOR(B, 0, SZ-1, 1){
            FOR(D, 0, SZ-1, 1){
                FOR(E, 0, SZ-1, 1){
                    FOR(H, 0, SZ-1, 1){
                        FOR(F, 0, SZ-1, 1){
                            FOR(C, 0, SZ-1, 1){

                                int BFC = (edge_cnt[B][F] * edge_cnt[B][C]) % mod;
                                int DHC = (edge_cnt[D][H] * edge_cnt[D][C]) % mod;
                                int EHF = (edge_cnt[E][H] * edge_cnt[E][F]) % mod;

                                int BDEHFC = (((BFC * DHC) % mod) * EHF) % mod;

                                res += (((half_cnt[B][D][E] * half_cnt[F][H][C]) % mod) * BDEHFC) % mod;
                                res %= mod;

                            }
                        }
                    }
                }
            }
        }

    }

    cout<<res<<'\n';

    return 0;

}

Subtask #1
0 / 21.0

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