Submission #257969

#	Time	Username	Problem	Language	Result	Execution time	Memory
257969		MrRobot_28	Trener (COCI20_trener)	C++17	110 / 110	723 ms	4672 KiB

trener

#include<bits/stdc++.h>
using namespace std;
const int const1 = 1e9 + 7;
const int const2 = 998244353;
vector <vector <vector <pair <int, int> > > > g;
vector <vector <bool> > used;
vector <vector <int> > dist;
int n, k;
	vector <vector <pair <pair <int, int>, pair <pair <int, int>, pair <int, int> > > > > hashes;
void dfs(int a, int b)
{
	used[a][b] = 1;
	if(a == 0)
	{
		dist[a][b] = 1;
		return;
	}
	for(int i = 0; i < k; i++)
	{
		if(hashes[a - 1][i].first == hashes[a][b].second.first || hashes[a - 1][i].first == hashes[a][b].second.second)
		{
			if(!used[a - 1][i])
			{
				dfs(a - 1, i);
			}
			dist[a][b] += dist[a - 1][i];
			if(dist[a][b] >= const1)
			{
				dist[a][b] -= const1;
			}
		}
	}
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> k;
	used.resize(n, vector <bool> (k));
	dist.resize(n, vector <int> (k));
	hashes.resize(n);
	vector <int> Pow(n + 1), Pow1(n + 1);
	Pow[0] = 1;
	Pow1[0] = 1;
	for(int i = 1; i <= n; i++)
	{
		Pow1[i] = 1LL * Pow1[i - 1] * 27 % const2;
		Pow[i] = 1LL* Pow[i - 1] * 27 % const1;
	}
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < k; j++)
		{
			string s;
			cin >> s;
			int hash1 = 0;
			int hash2 = 0;
			int hash3, hash4, hash5, hash6;
			for(int p = 0; p < i + 1; p++)
			{
				hash1 = (1LL * hash1 * 27 + s[p] - 'a' + 1) % const1;
				hash2 = (1LL * hash2 * 27 + s[p] - 'a' + 1) % const2;
			}
			hash3 = 0;
			hash4 = 0;
			for(int p = 1; p < i + 1; p++)
			{
				hash3 = (1LL * hash3 * 27 + s[p] - 'a' + 1) % const1;
				hash4 = (1LL * hash4 * 27 + s[p] - 'a' + 1) % const2;
			}
			hash5 = 0;
			hash6 = 0;
			for(int p = 0; p < i; p++)
			{
				hash5 = (1LL * hash5 * 27 + s[p] - 'a' + 1) % const1;
				hash6 = (1LL * hash6 * 27 + s[p] - 'a' + 1) % const2;
			}
			hashes[i].push_back({{hash1, hash2}, {{hash3, hash4}, {hash5, hash6}}});
		}
		sort(hashes[i].begin(), hashes[i].end());
	}
	int ans = 0;
	for(int i = 0;i < k; i++)
	{
		dfs(n - 1, i);
		ans += dist[n - 1][i];
		if(ans >= const1)
		{
			ans -= const1;
		}
	}
	cout << ans;
  	return 0;
}

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