oj.uz

Submission #845609

# Submission time Handle Problem Language Result Execution time Memory
845609 2023-09-06T14:27:22 Z vjudge1 Trener (COCI20_trener) C++11
0 / 110
 9 ms 1628 KB 
#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;
        // 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

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
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1628 KB Output is correct
2 Correct 9 ms 1624 KB Output is correct
3 Correct 8 ms 1628 KB Output is correct
4 Incorrect 3 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -