oj.uz

Submission #524532

# Submission time Handle Problem Language Result Execution time Memory
524532 2022-02-09T12:42:57 Z tato Trener (COCI20_trener) C++14
55 / 110
 2000 ms 9560 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(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.0 / 22.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 2992 KB Output is correct
2 Correct 52 ms 2908 KB Output is correct
3 Correct 59 ms 3268 KB Output is correct
4 Correct 47 ms 7800 KB Output is correct
5 Correct 53 ms 3132 KB Output is correct
6 Correct 52 ms 3120 KB Output is correct
7 Correct 50 ms 7748 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2124 KB Output is correct
2 Correct 1 ms 2124 KB Output is correct
3 Correct 1 ms 2124 KB Output is correct
4 Correct 1 ms 2124 KB Output is correct
5 Correct 53 ms 2992 KB Output is correct
6 Correct 52 ms 2908 KB Output is correct
7 Correct 59 ms 3268 KB Output is correct
8 Correct 47 ms 7800 KB Output is correct
9 Correct 53 ms 3132 KB Output is correct
10 Correct 52 ms 3120 KB Output is correct
11 Correct 50 ms 7748 KB Output is correct
12 Execution timed out 2081 ms 9560 KB Time limit exceeded
13 Halted 0 ms 0 KB -