Submission #524535

#	Time	Username	Problem	Language	Result	Execution time	Memory
524535		tato	Trener (COCI20_trener)	C++14	55 / 110	2069 ms	436836 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];
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] or v[m][i][0] == v[m+1][j][1])
			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: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 0 / 55