oj.uz

Submission #999010

# Submission time Handle Problem Language Result Execution time Memory
999010 2024-06-15T04:54:55 Z vjudge1 Trener (COCI20_trener) C++17
55 / 110
 429 ms 13704 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll N = 55, K = 1505;
const ll base = 727, mod = 1e9 + 7;

ll n, k, hsh[N][K], inv = 696011009, pwr[N];
vector<pair<ll, ll>> g[N][K];
map<ll, ll> cnt[N], dp[N];

int main(){
    pwr[0] = 1;
    for (ll i = 1; i < N; i ++)
        pwr[i] = (pwr[i - 1] * base) % mod;

    cin >> n >> k;
    for (ll i = 1; i <= n; i ++){
        for (ll j = 1; j <= k; j ++){
            string s;
            cin >> s;

            for (char c : s)
                hsh[i][j] = (hsh[i][j] * base + c) % mod;
            cnt[i][hsh[i][j]]++;
            dp[i][hsh[i][j]]++;
        }
    }

    // cout << endl;
    // for (int i = 1; i <= n; i ++){
    //     cout << i << " : ";
    //     for (auto [H, val] : dp[i])
    //         cout << H << " -- " << val << ", ";
    //     cout << endl;
    // }
    // cout << endl;

    for (ll i = n - 1; i > 0; i --){
        for (auto [H, C] : cnt[i]){
            ll sm = 0;
            // cout << "HASH = " << H << endl;
            map<int, bool> seen;
            for (int c = 'a'; c <= 'z'; c ++){
                ll nh = (H * base + c) % mod;
                // cout << "can have edge with " << nh << endl;
                if (!seen[nh] and dp[i + 1].find(nh) != dp[i + 1].end())
                    sm = (sm + dp[i + 1][nh]) % mod;
                seen[nh] = 1;

                nh = (H + pwr[i] * c) % mod;
                // cout << "can have edge with " << nh << endl;
                if (!seen[nh] and dp[i + 1].find(nh) != dp[i + 1].end())
                    sm = (sm + dp[i + 1][nh]) % mod;
                seen[nh] = 1;
            }

            dp[i][H] = C * sm % mod;
        }
    }

    // cout << endl;
    // for (int i = 1; i <= n; i ++){
    //     cout << i << " : ";
    //     for (auto [H, val] : dp[i])
    //         cout << H << " -- " << val << ", ";
    //     cout << endl;
    // }
    // cout << endl;

    ll ans = 0;
    for (auto [H, val] : dp[1])
        ans = (ans + val) % mod;
    cout << ans << endl;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3412 KB Output is correct
2 Correct 28 ms 3416 KB Output is correct
3 Correct 29 ms 3420 KB Output is correct
4 Correct 3 ms 2908 KB Output is correct
5 Correct 23 ms 3392 KB Output is correct
6 Correct 22 ms 3404 KB Output is correct
7 Correct 4 ms 2904 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 28 ms 3412 KB Output is correct
6 Correct 28 ms 3416 KB Output is correct
7 Correct 29 ms 3420 KB Output is correct
8 Correct 3 ms 2908 KB Output is correct
9 Correct 23 ms 3392 KB Output is correct
10 Correct 22 ms 3404 KB Output is correct
11 Correct 4 ms 2904 KB Output is correct
12 Incorrect 429 ms 13704 KB Output isn't correct
13 Halted 0 ms 0 KB -