Submission #257956

#	Time	Username	Problem	Language	Result	Execution time	Memory
257956		MrRobot_28	Trener (COCI20_trener)	C++17	55 / 110	1068 ms	524292 KiB

trener

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

Compilation message (stderr)

trener.cpp: In function 'void dfs(long long int, long long int)':
trener.cpp:17:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[a][b].size(); i++)
                 ~~^~~~~~~~~~~~~~~~
trener.cpp: In function 'int main()':
trener.cpp:90:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(it < mass1.size() && (mass1[it].first < hashes[i + 1][d].first || 
           ~~~^~~~~~~~~~~~~~
trener.cpp:95:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(it != mass1.size() && mass1[it] == hashes[i + 1][d])
        ~~~^~~~~~~~~~~~~~~

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