Submission #845735

#	Time	Username	Problem	Language	Result	Execution time	Memory
845735		vjudge1	Trener (COCI20_trener)	C++17	110 / 110	337 ms	336332 KiB

trener

#include <bits/stdc++.h>
#define int long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int (i) = 0; (i) < (n); (i)++)


using namespace std;

const double EPS = 0.00001;
const int INF = 1e9+500;
const int MOD = 1e9+7;
const int N = 55;
const int K = 1505;
const int ALPH = 26;
int n,m,q,k;
vector<vector<string> > names;
vector<vector<int> > res;
int add(int x, int y) {
    if(x+y < MOD) return x+y;
    return x+y-MOD; 
}
int mull(int x, int y) {
    return (x*y)%MOD;
}

struct TrieNode {
    TrieNode *c[ALPH];
    int val;
    TrieNode() {
        for(int i = 0; i<ALPH; i++) {
            c[i] = NULL;
        }
        val = 0;
    }
    
    void insert(string s, int num, int index) {
        if(index == s.size()) {
            val = add(val,num);
            return;
        }
        if(c[s[index] - 'a'] == NULL) {
        
            c[s[index] - 'a'] = new TrieNode();
        }
        c[s[index] - 'a']->insert(s,num, index+1);
    }

    int query(string s, int index) {
        if(index == s.size()) {
            return val;
        }
        if(c[s[index] - 'a'] == NULL) {
            return 0;
        }
        return c[s[index] - 'a']->query(s, index+1);
    }

};

void solve() {
    cin>>n>>k;
    res.resize(n+1, vector<int> (k));
    names.resize(n+1, vector<string> (k));
    for(int i = 1; i<=n; i++) {
        for(int j = 0; j<k; j++) {
            cin>>names[i][j];
        }
        
    }
    TrieNode *roots[N];
    for(int i = 1; i<=n; i++) {
        roots[i] = new TrieNode();
    }
    for(int i = 0; i <k; i++) {
        res[1][i] = 1;
    }

    for(int i = 1; i<n; i++) {
        for(int j = 0; j<k; j++) {
            //cout<<"i:"<<i<<" j:"<<j<<"\n";
            roots[i]->insert(names[i][j], res[i][j], 0);
            
        }
        for(int j = 0; j<k; j++) {
            string s = names[i+1][j].substr(0,i) ,t = names[i+1][j].substr(1,i);
            //cout<<"i:"<<i<<" j:"<<j<<"\n";
            res[i+1][j] = roots[i]->query(s, 0);
            if(s!=t) {
                res[i+1][j] = add(res[i+1][j] , roots[i]->query(t, 0));
            }
            
        }
    }
    int ans = 0;
    for(int i = 0; i<k; i++) {
        ans = add(ans , res[n][i]);
    }
    cout<<ans<<"\n";
}
 
signed main() {
    int test = 1;
    //cin>>test;
    while(test--) {
        solve();
    }
    
}

Compilation message (stderr)

trener.cpp: In member function 'void TrieNode::insert(std::string, long long int, long long int)':
trener.cpp:39: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]
   39 |         if(index == s.size()) {
      |            ~~~~~~^~~~~~~~~~~
trener.cpp: In member function 'long long int TrieNode::query(std::string, long long int)':
trener.cpp:51: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]
   51 |         if(index == s.size()) {
      |            ~~~~~~^~~~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 55 / 55