Submission #524541

#	Time	Username	Problem	Language	Result	Execution time	Memory
524541		tato	Trener (COCI20_trener)	C++14	0 / 110	62 ms	3656 KiB

trener

#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];
map <string,long long> g;
map <string,int> used;
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[v[par.first][par.second]]= 1;
	for(pair <int,int> i : gd[par.first][par.second])
		{
			long long cnt;
			if(used[v[i.first][i.second]]== 1)
				cnt = g[v[i.first][i.second]];
			else
			 cnt = dfs({i.first,i.second}, m + 1);
			g[v[par.first][par.second]] = (g[v[par.first][par.second]] + cnt) % p;
		}
			
	return  g[v[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(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
• Subtask 2: 0 / 33
• Subtask 3: 0 / 55