oj.uz

Submission #584217

# Submission time Handle Problem Language Result Execution time Memory
584217 2022-06-27T04:25:10 Z AGE Trener (COCI20_trener) C++14
55 / 110
 545 ms 524288 KB 
#include<bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define int long long
using namespace std;
const int N=1e6,M=2e3,mod=1e9+7,p=31;
int a[12]={31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
string s[51][M];
int hashh[51][M][3],ans[51][M];
vector<int>adj[51][M];

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

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

int summ(int x,int 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()
{
    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].pb(k);

            }
        }
    }

    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(auto x:adj[i][j]){
                ans[i][j]=summ(ans[i][j],ans[i+1][x]);
            }
        }
    }


    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(long long int, long long int)':
trener.cpp:30:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int k=1;k<s[i][j].size()-1;k++){
      |                 ~^~~~~~~~~~~~~~~~~
trener.cpp:41:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int k=1;k<s[i][j].size();k++){
      |                 ~^~~~~~~~~~~~~~~
trener.cpp:52:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int k=1;k<s[i][j].size();k++){
      |                 ~^~~~~~~~~~~~~~~
trener.cpp: At global scope:
trener.cpp:62:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   62 | main()
      | ^~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5900 KB Output is correct
2 Correct 3 ms 5908 KB Output is correct
3 Correct 3 ms 5844 KB Output is correct
4 Correct 3 ms 5920 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 6820 KB Output is correct
2 Correct 12 ms 6868 KB Output is correct
3 Correct 12 ms 6868 KB Output is correct
4 Correct 21 ms 11772 KB Output is correct
5 Correct 13 ms 7124 KB Output is correct
6 Correct 13 ms 7124 KB Output is correct
7 Correct 18 ms 11756 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5900 KB Output is correct
2 Correct 3 ms 5908 KB Output is correct
3 Correct 3 ms 5844 KB Output is correct
4 Correct 3 ms 5920 KB Output is correct
5 Correct 15 ms 6820 KB Output is correct
6 Correct 12 ms 6868 KB Output is correct
7 Correct 12 ms 6868 KB Output is correct
8 Correct 21 ms 11772 KB Output is correct
9 Correct 13 ms 7124 KB Output is correct
10 Correct 13 ms 7124 KB Output is correct
11 Correct 18 ms 11756 KB Output is correct
12 Correct 417 ms 17388 KB Output is correct
13 Correct 406 ms 17304 KB Output is correct
14 Correct 438 ms 17180 KB Output is correct
15 Correct 405 ms 17328 KB Output is correct
16 Runtime error 545 ms 524288 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -