oj.uz

Submission #524609

# Submission time Handle Problem Language Result Execution time Memory
524609 2022-02-09T15:59:55 Z tato Trener (COCI20_trener) C++14
0 / 110
 36 ms 5968 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;

int n,k;
vector <string> v[51];
map <string,int> used;
set <string>  gd[51][1501];
ll p = 1e9+7;
map <string, ll> g;

bool check(string s, string l)
{
	int ind1 = 0, ind = 0;

	int ss = s.size();
	for(int i = 0; i < ss; i++)
		if(s[i] != l[i + 1])
			{
				ind = 1;
				break;
			}
	for(int i = 0; i < ss; i++)
		if(s[i] != l[i])
			{
				ind1 = 1;
				break;
			}
	
	if(ind == 1 and ind1 == 1)
		return false;
	else
		return true;
}
void answer()
{
	
	string s;
	cin >> n >> k;
	
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= k; j++)
			{
				cin >> s;
				v[i].pb(s);
			}
	for(int i = 0; i < k; i++)
		used[v[1][i]] = 1;
		
	for(int m = 1 ; m < n; m++)
		for(int i = 0; i < k; i++)
			if(used[v[m][i]] == 1)
			for(int j = 0; j < k; j++)
				{
					if(check(v[m][i], v[m+1][j]))
						{
							gd[m][i].insert(v[m+1][j]);
							used[v[m+1][j]] = 1;
						}
				}
	
	for(int i = 0; i < k; i++)
	if(used[v[n][i]] == 1)
		g[v[n][i]] = 1;
		
	for(int m = n - 1; m > 0; m--)
		for(int i = 0; i < k; i++)
			if(used[v[m][i]] == 1)
			for(auto it = gd[m][i].begin(); it != gd[m][i].end(); it++ )
				if(g[*it] != 0 )
					g[v[m][i]] = (g[v[m][i]] + g[*it]) % p;
					
	ll pas = 0;
	
				
	for(int i = 0; i < k; i++)
		pas = (pas + g[v[1][i]]) % p;
		
	cout << pas;
}

int main()
{
	int t = 1;
	
	//cin >> t;
	
	while(t--)
		answer();
	
	return 0;
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3884 KB Output is correct
2 Incorrect 2 ms 3788 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 5968 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3884 KB Output is correct
2 Incorrect 2 ms 3788 KB Output isn't correct
3 Halted 0 ms 0 KB -