Submission #845614

#	Time	Username	Problem	Language	Result	Execution time	Memory
845614		vjudge1	Trener (COCI20_trener)	C++11	110 / 110	139 ms	19316 KiB

trener

#include <bits/stdc++.h>
#define lg(a) (31 - __builtin_clz((a)))
#define endl ("\n")
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define vi vector<int>
#define st first
#define nd second
#define all(aa) aa.begin(), aa.end()
#define rall(aa) aa.rbegin(), aa.rend()
#define forn(i, n) for(int i=0;i<n;i++)
#define trav(e, x) for(auto& e:x)
#define until(n, v) (int) (lower_bound(v.begin(), v.end(), n)-v.begin()) //# of elements < n
#define after(n, v) (int) (v.end()-upper_bound(v.begin(), v.end(), n))   //# of elements > n
#define sameas(n, v) (int) (upper_bound(v.begin(), v.end(), n) - lower_bound(v.begin(), v.end(), n)) //# of elements ==n
typedef long long ll;
const ll MOD = 1e9+7;
using namespace std;
/*

*/

map<string, ll> dp;
map<string, int> cnt;
vector<set<string>> v;

ll d(string s){
    if(dp.count(s)) return (dp[s]%MOD);
    // cout<<s<<endl;
    if(v[s.size()-1].count(s)==0) return 0;
    string left, right;
    for(int i=0;i<s.size()-1;i++){
        left.pb(s[i]);
    }
    for(int i=1;i<s.size();i++){
        right.pb(s[i]);
    }
    if(right==left) return (d(right)%MOD)*(cnt[right]%MOD)%MOD;
    return dp[s] = (((cnt[left]%MOD)*(d(left)%MOD) + (cnt[right]%MOD)*(d(right)%MOD))%MOD);
}


void solve(){
    int n, k; cin>>n>>k;
    v.resize(n);
    for(int i=0;i<n*k;i++){
        string a; cin>>a;
        cnt[a]++;
        v[a.size()-1].insert(a);
        if(a.size()==1) dp[a]=1;
    }
    ll ans=0;
    for(auto e : v[n-1]){
        ans = (ans+ (d(e)%MOD)*(cnt[e]%MOD))%MOD;
        // cout<<e<<' '<<d(e)<<' '<<d(e)<<d(e)<<endl;
    }
    cout<<ans<<endl;

}

int main(){
	int test; 
    // cin >> test;
    test =1;
   	while (test--){
		solve();
    }
}

Compilation message (stderr)

trener.cpp: In function 'll d(std::string)':
trener.cpp:34:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i=0;i<s.size()-1;i++){
      |                 ~^~~~~~~~~~~
trener.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i=1;i<s.size();i++){
      |                 ~^~~~~~~~~

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