oj.uz

Submission #238577

# Submission time Handle Problem Language Result Execution time Memory
238577 2020-06-11T22:42:50 Z vankata Trener (COCI20_trener) C++14
110 / 110
 921 ms 9208 KB 
#include<bits/stdc++.h>
using namespace std;

struct tri
{
    int x,y,z;
    tri() {};
    tri(int a,int b,int c)
    {
        x=a;
        y=b;
        z=c;
    }
    bool operator <(const tri &t)const
    {
        if(t.x==x)
        {
            if(t.y==y)
            {
                return z<t.z;
            }
            return y<t.y;
        }
        return x<t.x;
    }
    bool operator ==(const tri &t)const
    {
        return t.x==x&&t.y==y&&t.z==z;
    }
};

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

tri h[64][MAXN];
long long dp[64][MAXN];

tri hsh(string s)
{
    int l,i;
    long long base[3]= {29,31,37};
    long long mod[3]= {(int)(1e7+7),(int)(1e9+7),(int)(1e9+9)};
    long long h1[3]= {0,0,0};
    for(i=0; i<s.size(); i++)
    {
        for(l=0; l<3; l++)
        {
            h1[l]*=base[l];
            h1[l]+=(s[i]-'a'+1);
            h1[l]%=mod[l];
        }
    }
    return {h1[0],h1[1],h1[2]};
}

vector<string>v[64];
long long n,k;

void solve()
{
    int i,j,l;
    tri t1,t2;
    string t,q;
    for(i=0; i<k; i++)dp[0][i]=1;
    for(i=1; i<n; i++)
    {
        for(j=0; j<k; j++)
        {
            t=v[i][j].substr(0,i);
            q=v[i][j].substr(1);
            t1=hsh(t);
            t2=hsh(q);
            for(l=0; l<k; l++)
            {
                if(h[i-1][l]==t1||h[i-1][l]==t2)
                {
                    dp[i][j]+=dp[i-1][l];
                    dp[i][j]%=MOD;
                }
            }
        }
    }
    long long ans = 0;
    for(i=0; i<k; i++)
    {
        ans+=dp[n-1][i];
        ans%=MOD;
    }
    cout<<ans<<"\n";
}

void read()
{
    int i,j;
    string s;
    cin>>n>>k;

    for(i=0; i<n; i++)
    {
        for(j=0; j<k; j++)
        {
            cin>>s;
            v[i].push_back(s);
            h[i][j]=hsh(s);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    read();
    solve();
    return 0;
}

Compilation message

trener.cpp: In function 'tri hsh(std::__cxx11::string)':
trener.cpp:44:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<s.size(); i++)
              ~^~~~~~~~~
trener.cpp:53:17: warning: narrowing conversion of 'h1[0]' from 'long long int' to 'int' inside { } [-Wnarrowing]
     return {h1[0],h1[1],h1[2]};
             ~~~~^
trener.cpp:53:23: warning: narrowing conversion of 'h1[1]' from 'long long int' to 'int' inside { } [-Wnarrowing]
     return {h1[0],h1[1],h1[2]};
                   ~~~~^
trener.cpp:53:29: warning: narrowing conversion of 'h1[2]' from 'long long int' to 'int' inside { } [-Wnarrowing]
     return {h1[0],h1[1],h1[2]};
                         ~~~~^

Subtask #1
22.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 Correct 5 ms 512 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1152 KB Output is correct
2 Correct 14 ms 1152 KB Output is correct
3 Correct 14 ms 1152 KB Output is correct
4 Correct 17 ms 1152 KB Output is correct
5 Correct 14 ms 1152 KB Output is correct
6 Correct 14 ms 1280 KB Output is correct
7 Correct 17 ms 1280 KB Output is correct

Subtask #3
55.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 Correct 5 ms 512 KB Output is correct
5 Correct 14 ms 1152 KB Output is correct
6 Correct 14 ms 1152 KB Output is correct
7 Correct 14 ms 1152 KB Output is correct
8 Correct 17 ms 1152 KB Output is correct
9 Correct 14 ms 1152 KB Output is correct
10 Correct 14 ms 1280 KB Output is correct
11 Correct 17 ms 1280 KB Output is correct
12 Correct 266 ms 9208 KB Output is correct
13 Correct 260 ms 9120 KB Output is correct
14 Correct 266 ms 8936 KB Output is correct
15 Correct 263 ms 8952 KB Output is correct
16 Correct 921 ms 8952 KB Output is correct
17 Correct 294 ms 9100 KB Output is correct
18 Correct 293 ms 8952 KB Output is correct
19 Correct 293 ms 8928 KB Output is correct
20 Correct 293 ms 8952 KB Output is correct
21 Correct 293 ms 8952 KB Output is correct
22 Correct 921 ms 9056 KB Output is correct