oj.uz

Submission #1048571

# Submission time Handle Problem Language Result Execution time Memory
1048571 2024-08-08T08:27:45 Z andrey27_sm Cubeword (CEOI19_cubeword) C++17
0 / 100
 43 ms 7940 KB 
//#pragma GCC optimze("O3,unroll-loops")
//#pragma GCC target("avx,avx2,bmi,bmi2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll mod = 998244353;
int tmp[62][62][62];
inline ll solve(vector<string> words){
    map<pair<char,char>,set<string>> mp;
    set<char> st;
    for(auto& word : words){
        st.insert(word[0]);
        st.insert(word.back());
        mp[{word[0],word.back()}].insert(word);
        reverse(word.begin(),word.end());
        mp[{word[0],word.back()}].insert(word);
        reverse(word.begin(),word.end());
    }
    vector<int> links(128,-1);
    int n = st.size();
    vector<vector<ll>> indeg(n,vector<ll>(n,0));
    {
        int i = 0;
        for(auto& c : st){
            links[c] = i++;
        }
    }
    for(auto& [k,v] : mp){
        if(v.size() > 0){
            indeg[links[k.first]][links[k.second]]+=v.size();
        }
    }
    for(int k = 0; k < n; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                tmp[i][j][k] = 0;
                for(int l = 0; l < n; l++){
                    ll ans1 = (ll)indeg[k][l] * indeg[i][l];
                    ans1%=mod;
                    ans1*=indeg[j][l];
                    ans1%=mod;
                    tmp[i][j][k] = (tmp[i][j][k] + ans1) % mod;
                }
            }
        }
    }
    ll ans = 0;
    for(int i = 0; i < n; i++){ // top
        for(int j = 0; j < n; j++){ // top
            for(int k = 0; k < n; k++){ // bot
                for (int l = 0; l < n; ++l) { // bot
                    ll ans_tmp = tmp[i][j][k]*tmp[i][j][l];
                    ans_tmp%=mod;
                    ans_tmp*=tmp[i][k][l];
                    ans_tmp%=mod;
                    ans_tmp*=tmp[j][k][l];
                    ans_tmp%=mod;
                    ans = (ans + ans_tmp) % mod;
                }
            }
        }
    }
    return ans;
}
inline void solve(){
    int n;
    cin >> n;
    vector<vector<string>> words(11,vector<string>());
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        words[s.size()].push_back(s);
    }
    ll ans = 0;
    for(int i = 1; i <= 10; i++){
        if(words[i].empty()) continue;
        ans = (ans + solve(words[i])) % mod;
    }
    cout << ans << "\n";

}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while(t--)
        solve();
}

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 7940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 7940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 7940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 7940 KB Output isn't correct
2 Halted 0 ms 0 KB -