oj.uz

Submission #584218

# Submission time Handle Problem Language Result Execution time Memory
584218 2022-06-27T04:25:43 Z AGE Trener (COCI20_trener) C++14
55 / 110
 455 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[55][M];
int hashh[55][M][3],ans[55][M];
vector<int>adj[55][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 3 ms 6356 KB Output is correct
2 Correct 5 ms 6356 KB Output is correct
3 Correct 3 ms 6356 KB Output is correct
4 Correct 3 ms 6356 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 7252 KB Output is correct
2 Correct 13 ms 7332 KB Output is correct
3 Correct 12 ms 7244 KB Output is correct
4 Correct 21 ms 12104 KB Output is correct
5 Correct 13 ms 7500 KB Output is correct
6 Correct 13 ms 7508 KB Output is correct
7 Correct 19 ms 12144 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6356 KB Output is correct
2 Correct 5 ms 6356 KB Output is correct
3 Correct 3 ms 6356 KB Output is correct
4 Correct 3 ms 6356 KB Output is correct
5 Correct 13 ms 7252 KB Output is correct
6 Correct 13 ms 7332 KB Output is correct
7 Correct 12 ms 7244 KB Output is correct
8 Correct 21 ms 12104 KB Output is correct
9 Correct 13 ms 7500 KB Output is correct
10 Correct 13 ms 7508 KB Output is correct
11 Correct 19 ms 12144 KB Output is correct
12 Correct 413 ms 17728 KB Output is correct
13 Correct 407 ms 17740 KB Output is correct
14 Correct 420 ms 17596 KB Output is correct
15 Correct 421 ms 17840 KB Output is correct
16 Runtime error 455 ms 524288 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -