Submission #238577

#	Time	Username	Problem	Language	Result	Execution time	Memory
238577		vankata	Trener (COCI20_trener)	C++14	110 / 110	921 ms	9208 KiB

trener

#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 (stderr)

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 / 22
• Subtask 2: 33 / 33
• Subtask 3: 55 / 55