oj.uz

Submission #959685

# Submission time Handle Problem Language Result Execution time Memory
959685 2024-04-08T18:43:34 Z Cadoc Trener (COCI20_trener) C++14
55 / 110
 518 ms 524288 KB 
/*
    Author: Cadocx
    Codeforces: https://codeforces.com/profile/Kadoc
    VNOJ: oj.vnoi.info/user/Cadoc
*/

#include <bits/stdc++.h>
using namespace std;

// input/output
#define fastIO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define el cout << '\n'
#define execute cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s"
// #pragma GCC optimize("O2")
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
//data type
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define piv pair<int, vector<int>>
#define vi vector<int>
#define vl vector<ll>
#define vc vector<char>
//STL
#define sz(x) (int)(x).size()
#define for1(i,l,r) for(auto i = l; i <= r; i++)
#define for2(i,r,l) for(auto i = r; i >= l; i--)
#define forin(i,a) for(auto i : a)
#define pb push_back
#define eb emplace_back
#define pf push_front
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
//bitmask
#define bitcnt(n) __builtin_popcount(n)
#define mask(i) (1 << (i))
#define bit(n, i) (((n) >> (i)) & 1)
#define set_on(n, i) ((n) | mask(i))
#define set_off(n, i) ((n) & ~mask(i))
//constant
#define N 3000005
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define base 31
#define Kadoc 0

int n, k;
ll f[N], h[55][1505][3], pw[N];
vector<int> a[N];

ll calc(int u){
    if((n-1)*k < u && u <= n*k) return f[u] = 1;
    ll &ans = f[u];
    if(ans != -1) return ans % MOD;
    ans = 0;
    for(int v:a[u]) (ans += calc(v)) %= MOD;
    return ans % MOD;
}

void solve(){
    cin >> n >> k;
    pw[0] = 1;
    for(int i=1; i<=n; ++i) pw[i] = pw[i-1] * base % MOD;
    for(int i=1; i<=n; ++i) for(int j=1; j<=k; ++j){
        string s; cin >> s;
        ll cur = 0, pre = 0;
        for(char c:s){
            h[i][j][1] = pre;
            cur = (pre*base % MOD + c-'a'+1) % MOD;
            pre = cur;
        }
        h[i][j][0] = cur;
        if(i==1) continue;
        pre = cur = 0;
        for(int v=1; v<i; ++v) cur = (pre*base % MOD + s[v]-'a'+1) % MOD, pre = cur;
        h[i][j][2] = cur;
    }

    for(int i=1; i<=k; ++i) a[0].pb(i);
    for(int i=1; i<n; ++i){
        for(int j=1; j<=k; ++j){
            for(int v=1; v<=k; ++v) if(h[i][j][0] == h[i+1][v][1] || h[i][j][0] == h[i+1][v][2]){
                a[(i-1)*k + j].pb(i*k + v);
            }
        }
    }

    for(int i=0; i<=n*k; ++i){
        f[i] = -1;
        if(!a[i].size()) continue;
        a[i].resize(unique(all(a[i])) - a[i].begin());
    }

    calc(0);
    cout << f[0] % MOD;
}

int main(){
    #define NAME "TASK"
    if(fopen(NAME".inp", "r")){
        freopen(NAME".inp", "r", stdin);
        freopen(NAME".out", "w", stdout);
    }

    fastIO;
    
    if(Kadoc){
        int tc; cin >> tc;
        while(tc--){
            solve();
        }
    } else solve();
}

Compilation message

trener.cpp: In function 'int main()':
trener.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen(NAME".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
trener.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen(NAME".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 72276 KB Output is correct
2 Correct 16 ms 70744 KB Output is correct
3 Correct 18 ms 72284 KB Output is correct
4 Correct 17 ms 70864 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 71384 KB Output is correct
2 Correct 20 ms 71512 KB Output is correct
3 Correct 21 ms 71260 KB Output is correct
4 Correct 27 ms 73920 KB Output is correct
5 Correct 21 ms 71512 KB Output is correct
6 Correct 22 ms 71596 KB Output is correct
7 Correct 29 ms 73892 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 72276 KB Output is correct
2 Correct 16 ms 70744 KB Output is correct
3 Correct 18 ms 72284 KB Output is correct
4 Correct 17 ms 70864 KB Output is correct
5 Correct 21 ms 71384 KB Output is correct
6 Correct 20 ms 71512 KB Output is correct
7 Correct 21 ms 71260 KB Output is correct
8 Correct 27 ms 73920 KB Output is correct
9 Correct 21 ms 71512 KB Output is correct
10 Correct 22 ms 71596 KB Output is correct
11 Correct 29 ms 73892 KB Output is correct
12 Correct 170 ms 77404 KB Output is correct
13 Correct 164 ms 77348 KB Output is correct
14 Correct 173 ms 77540 KB Output is correct
15 Correct 166 ms 77392 KB Output is correct
16 Runtime error 518 ms 524288 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -