oj.uz

Submission #257956

# Submission time Handle Problem Language Result Execution time Memory
257956 2020-08-05T06:23:44 Z MrRobot_28 Trener (COCI20_trener) C++17
55 / 110
 1068 ms 524292 KB 
#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

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

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 760 KB Output is correct
2 Correct 24 ms 928 KB Output is correct
3 Correct 24 ms 896 KB Output is correct
4 Correct 36 ms 5656 KB Output is correct
5 Correct 24 ms 1024 KB Output is correct
6 Correct 33 ms 1016 KB Output is correct
7 Correct 34 ms 5752 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 23 ms 760 KB Output is correct
6 Correct 24 ms 928 KB Output is correct
7 Correct 24 ms 896 KB Output is correct
8 Correct 36 ms 5656 KB Output is correct
9 Correct 24 ms 1024 KB Output is correct
10 Correct 33 ms 1016 KB Output is correct
11 Correct 34 ms 5752 KB Output is correct
12 Correct 604 ms 9828 KB Output is correct
13 Correct 575 ms 9720 KB Output is correct
14 Correct 587 ms 9976 KB Output is correct
15 Correct 586 ms 9976 KB Output is correct
16 Runtime error 1068 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -