oj.uz

Submission #524534

# Submission time Handle Problem Language Result Execution time Memory
524534 2022-02-09T12:46:31 Z tato Trener (COCI20_trener) C++14
0 / 110
 8 ms 2552 KB 
#include <bits/stdc++.h>

using namespace std;





long long p = 1e9+7;
map <string, long long > mp;
long long pas = 0;
int n,k;
vector <string > v[51];
long long g[51][1501];
int used[51][1501];
vector <pair<int,int> > gd[51][1501];
bool check(string s, string l)
{
	

	if(s == l.substr(0,l.size() - 1) or s == l.substr(1))
		return true;
	else
		return false;
	
}

long long dfs(pair <int,int> par,int m)
{
	if(m == n + 1)
		return 1;
	
	used[par.first][par.second] = 1;
	for(pair <int,int> i : gd[par.first][par.second])
		{
			long long cnt;
			if(used[i.first][i.second] == 1)
				cnt = g[i.first][i.second];
			else
			 cnt = dfs({i.first,i.second}, m + 1);
			g[par.first][par.second] = (g[par.first][par.second] + cnt) % p;
		}
			
	return  g[par.first][par.second];
	
	
}

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].push_back(s);
			}
	for(int m = 1; m < n; m++)	
	for(int i = 0; i < k; i++)
		{
			for(int j = 0; j < k; j++)
				if(v[m][i][0] == v[m+1][j][0])
			if(check(v[m][i], v[m+1][j]))
				gd[m][i].push_back({m+1,j});
					
		}
			
	
	for (int i = 0; i < k; i++)
		pas = (dfs({1,i},2) + pas) % 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 Incorrect 1 ms 2124 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

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

Subtask #3
0 / 55.0

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