oj.uz

Submission #584222

# Submission time Handle Problem Language Result Execution time Memory
584222 2022-06-27T04:33:56 Z AGE Trener (COCI20_trener) C++14
110 / 110
 1314 ms 117012 KB 
#include<bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ll long long
using namespace std;
const int N=1e6,M=1502,mod=1e9+7,p=31;
string s[55][M];
int hashh[55][M][3],ans[55][M];
bool adj[52][M][M];

int mult(ll x,ll y){
    return ((x%mod)*(y%mod))%mod;
}

int minuss(ll x,ll y){
    return ((x%mod)-(y%mod)+mod)%mod;
}

int summ(ll x,ll y){
    return ((x%mod)+(y%mod))%mod;
}

void compute_hash(int i,int j){

    int hash_val=0;
    int p_pow=1;
    hash_val=s[i][j][0]-'a'+1;
    for(int k=1;k<s[i][j].size()-1;k++){

        p_pow=mult(p_pow,p);
        hash_val=summ(hash_val,mult(s[i][j][k]-'a'+1,p_pow));

    }

    hashh[i][j][0]=hash_val;
    hash_val=0;
    p_pow=1;

    for(int k=1;k<s[i][j].size();k++){

        hash_val=summ(hash_val,mult(s[i][j][k]-'a'+1,p_pow));
        p_pow=mult(p_pow,p);

    }

    hashh[i][j][1]=hash_val;

    hash_val=s[i][j][0]-'a'+1;
    p_pow=1;
    for(int k=1;k<s[i][j].size();k++){

        p_pow=mult(p_pow,p);
        hash_val=summ(hash_val,mult(s[i][j][k]-'a'+1,p_pow));

    }

    hashh[i][j][2]=hash_val;

}
main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n,m;
    cin>>n>>m;

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>s[i][j];

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
            compute_hash(i,j);
    }

    for(int i=0;i<n-1;i++){
        for(int j=0;j<m;j++){
            for(int k=0;k<m;k++){

                if(hashh[i][j][2]==hashh[i+1][k][0]||hashh[i][j][2]==hashh[i+1][k][1])
                    adj[i][j][k]=1;

            }
        }
    }

    for(int j=0;j<m;j++)
        ans[n-1][j]=1;

    for(int i=n-2;i>=0;i--){
        for(int j=0;j<m;j++){
                for(int k=0;k<m;k++){
                    if(adj[i][j][k]==1)
                        ans[i][j]=summ(ans[i][j],ans[i+1][k]);
            }
        }
    }


    int sum=0;

    for(int i=0;i<m;i++)
        sum=summ(sum,ans[0][i]);

    cout<<sum<<endl;


    return 0;
}

Compilation message

trener.cpp: In function 'void compute_hash(int, int)':
trener.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int k=1;k<s[i][j].size()-1;k++){
      |                 ~^~~~~~~~~~~~~~~~~
trener.cpp:40:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int k=1;k<s[i][j].size();k++){
      |                 ~^~~~~~~~~~~~~~~
trener.cpp:51:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int k=1;k<s[i][j].size();k++){
      |                 ~^~~~~~~~~~~~~~~
trener.cpp: At global scope:
trener.cpp:61:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   61 | main()
      | ^~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10620 KB Output is correct
2 Correct 9 ms 10580 KB Output is correct
3 Correct 10 ms 10580 KB Output is correct
4 Correct 14 ms 11092 KB Output is correct
5 Correct 11 ms 10836 KB Output is correct
6 Correct 10 ms 10836 KB Output is correct
7 Correct 16 ms 11092 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 1 ms 3028 KB Output is correct
3 Correct 1 ms 3028 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 10 ms 10620 KB Output is correct
6 Correct 9 ms 10580 KB Output is correct
7 Correct 10 ms 10580 KB Output is correct
8 Correct 14 ms 11092 KB Output is correct
9 Correct 11 ms 10836 KB Output is correct
10 Correct 10 ms 10836 KB Output is correct
11 Correct 16 ms 11092 KB Output is correct
12 Correct 368 ms 108352 KB Output is correct
13 Correct 367 ms 108768 KB Output is correct
14 Correct 388 ms 108344 KB Output is correct
15 Correct 358 ms 108968 KB Output is correct
16 Correct 1313 ms 117012 KB Output is correct
17 Correct 409 ms 115320 KB Output is correct
18 Correct 448 ms 115304 KB Output is correct
19 Correct 404 ms 115532 KB Output is correct
20 Correct 425 ms 115456 KB Output is correct
21 Correct 426 ms 115468 KB Output is correct
22 Correct 1314 ms 116976 KB Output is correct