oj.uz

Submission #238575

# Submission time Handle Problem Language Result Execution time Memory
238575 2020-06-11T22:12:09 Z vankata Trener (COCI20_trener) C++14
0 / 110
 23 ms 1152 KB 
#include<bits/stdc++.h>
using namespace std;

const long long  MAXN = 2048;
const long long  MOD = (long long )(1e9+7);

map< pair< pair<long long,long long> ,long long > ,long long >mp;

long long n,k;

bool cmp(string a,string b)
{
    for(size_t i=0;i<a.size();i++)
    {
        if(a[i]!=b[i])return false;
    }return true;
}

long long  base1 = 29 ;
long long  base2 = 31 ;
long long base3=37;
long long  mod1=1e5+3;
long long  mod2=100019;
long long mod3=100043;

pair< pair<long long,long long > ,long long > hsh(string s)
{
    long long  i,j;
    long long  h1=0,h2=0,h3=0;
    for(i=0;i<s.size();i++)
    {
        h1*=base1;
        h2*=base2;
        h3*=base3;
        h1+=(s[i]-'a'+1);
        h2+=(s[i]-'a'+1);
        h3+=(s[i]-'a'+1);
        h1%=mod1;
        h2%=mod2;
        h3%=mod3;
    }
    return {{h1,h3},h2};
}

void read()
{
    long long  i,j,l;
    long long ans = 0;
    cin>>n>>k;
    string s,t,q;
    long long  lm=0;
    for(i=0;i<n;i++)
    {
        for(j=0;j<k;j++)
        {
            cin>>s;

            if(!i){mp[hsh(s)]++;continue;}

            t="";
            q="";
            t=s.substr(0,s.size()-1);
            q=s.substr(1);

            mp[hsh(s)]+=mp[hsh(q)];
            if(!cmp(q,t))mp[hsh(s)]+=mp[hsh(t)];
            mp[hsh(s)]%=MOD;
            if(i==n-1)
            {
                ans+=mp[hsh(s)];
                ans%=MOD;
            }
        }
    }
    if(n==1)
    {
        cout<<k<<'\n';
        return ;
    }
    cout<<ans<<'\n';
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    read();
    return 0;
}

Compilation message

trener.cpp: In function 'std::pair<std::pair<long long int, long long int>, long long int> hsh(std::__cxx11::string)':
trener.cpp:30:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<s.size();i++)
             ~^~~~~~~~~
trener.cpp:28:18: warning: unused variable 'j' [-Wunused-variable]
     long long  i,j;
                  ^
trener.cpp: In function 'void read()':
trener.cpp:47:20: warning: unused variable 'l' [-Wunused-variable]
     long long  i,j,l;
                    ^
trener.cpp:51:16: warning: unused variable 'lm' [-Wunused-variable]
     long long  lm=0;
                ^~

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Incorrect 5 ms 384 KB Output isn't correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1024 KB Output is correct
2 Correct 22 ms 1152 KB Output is correct
3 Correct 22 ms 1024 KB Output is correct
4 Incorrect 14 ms 512 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Incorrect 5 ms 384 KB Output isn't correct