oj.uz

Submission #524531

# Submission time Handle Problem Language Result Execution time Memory
524531 2022-02-09T12:33:03 Z tato Trener (COCI20_trener) C++14
55 / 110
 2000 ms 9576 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)
{
	
	string t = l.substr(0,l.size() - 1);
	string f = l.substr(1);
	if(s == t or s == f)
		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 55 ms 3016 KB Output is correct
2 Correct 52 ms 2908 KB Output is correct
3 Correct 52 ms 2996 KB Output is correct
4 Correct 60 ms 7792 KB Output is correct
5 Correct 52 ms 3108 KB Output is correct
6 Correct 69 ms 3232 KB Output is correct
7 Correct 59 ms 7808 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 55 ms 3016 KB Output is correct
6 Correct 52 ms 2908 KB Output is correct
7 Correct 52 ms 2996 KB Output is correct
8 Correct 60 ms 7792 KB Output is correct
9 Correct 52 ms 3108 KB Output is correct
10 Correct 69 ms 3232 KB Output is correct
11 Correct 59 ms 7808 KB Output is correct
12 Execution timed out 2066 ms 9576 KB Time limit exceeded
13 Halted 0 ms 0 KB -