Submission #845572

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
845572	2023-09-06T14:12:52 Z	vjudge1	Trener (COCI20_trener)	C++17	110 / 110	183 ms	16796 KB

trener

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define int long long
const int mod = 1e9 + 7;
inline long long get1(string const& s) {
    const int p = 29;
    const int m = 1e9 + 7;
    long long hash_value = 0;
    long long p_pow = 1;
    for (char c : s) {
        hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
        p_pow = (p_pow * p) % m;
    }
    return hash_value;
}
inline long long get2(string const& s) {
    const int p = 37;
    const int m = 1e9 + 7;
    long long hash_value = 0;
    long long p_pow = 1;
    for (char c : s) {
        hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
        p_pow = (p_pow * p) % m;
    }
    return hash_value;
}
inline long long get3(string const& s) {
    const int p = 41;
    const int m = 1e9 + 7;
    long long hash_value = 0;
    long long p_pow = 1;
    for (char c : s) {
        hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
        p_pow = (p_pow * p) % m;
    }
    return hash_value;
}
inline array < int , 3 > get(string const& s){
	return {get1(s),get2(s),get3(s)};
}
void solve(){
	int n,k;cin >> n >> k;
	string v[n+1][k];
	map < array < int , 3 > , int > mpa;
	for(int i = 1;i<=n;i++){
		for(int j = 0;j<k;j++){
			cin >> v[i][j];
		}
	}
	for(int i = 0;i<k;i++)mpa[get(v[1][i])]++;
	for(int i = 2;i<=n;i++){
		for(int j = 0;j<k;j++){
			string s1 = string(v[i][j].begin() , v[i][j].end()-1) , s2 = string(v[i][j].begin()+1 , v[i][j].end());
			array < int , 3 > myhash = get(v[i][j]);
			array < int , 3 > childhash0 = get(s1);
			array < int , 3 > childhash1 = get(s2);
			if(childhash0 == childhash1){
				mpa[myhash] = (mpa[myhash] + mpa[childhash0]) % mod;
			}
			else{
				mpa[myhash] = (mpa[myhash] + mpa[childhash0] + mpa[childhash1]) % mod;
			}	
			//cout << v[i][j] << " " << mpa[myhash] << endl;
		}
	}
	set < array < int , 3 > > ste;
	for(int i = 0;i<k;i++)ste.insert(get(v[n][i]));
	int ans = 0;
	for(auto itr : ste)ans = (ans + mpa[itr]) % mod;
	cout << ans << endl;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}

Subtask #1

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct

Subtask #2

33.0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	1372 KB	Output is correct
2	Correct	10 ms	1376 KB	Output is correct
3	Correct	9 ms	1372 KB	Output is correct
4	Correct	7 ms	604 KB	Output is correct
5	Correct	11 ms	1116 KB	Output is correct
6	Correct	9 ms	1116 KB	Output is correct
7	Correct	7 ms	604 KB	Output is correct

Subtask #3

55.0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	10 ms	1372 KB	Output is correct
6	Correct	10 ms	1376 KB	Output is correct
7	Correct	9 ms	1372 KB	Output is correct
8	Correct	7 ms	604 KB	Output is correct
9	Correct	11 ms	1116 KB	Output is correct
10	Correct	9 ms	1116 KB	Output is correct
11	Correct	7 ms	604 KB	Output is correct
12	Correct	183 ms	16460 KB	Output is correct
13	Correct	166 ms	16464 KB	Output is correct
14	Correct	179 ms	16796 KB	Output is correct
15	Correct	169 ms	16472 KB	Output is correct
16	Correct	96 ms	5468 KB	Output is correct
17	Correct	146 ms	12504 KB	Output is correct
18	Correct	151 ms	12540 KB	Output is correct
19	Correct	150 ms	12544 KB	Output is correct
20	Correct	155 ms	12456 KB	Output is correct
21	Correct	149 ms	12372 KB	Output is correct
22	Correct	98 ms	5464 KB	Output is correct