oj.uz

Submission #524549

# Submission time Handle Problem Language Result Execution time Memory
524549 2022-02-09T13:16:35 Z tato Trener (COCI20_trener) C++14
55 / 110
 2000 ms 10072 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];
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;
	if(used[v[par.first][par.second]] == 1)
		return g[v[par.first][par.second]];
		
	used[v[par.first][par.second]] = 1;
	
	for(pair <int,int> i : gd[par.first][par.second])
		{
		
			long long 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
22.0 / 22.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 3432 KB Output is correct
2 Correct 57 ms 3628 KB Output is correct
3 Correct 60 ms 3544 KB Output is correct
4 Correct 47 ms 7512 KB Output is correct
5 Correct 60 ms 3648 KB Output is correct
6 Correct 61 ms 3740 KB Output is correct
7 Correct 52 ms 7536 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1996 KB Output is correct
2 Correct 1 ms 1996 KB Output is correct
3 Correct 2 ms 2084 KB Output is correct
4 Correct 1 ms 1996 KB Output is correct
5 Correct 62 ms 3432 KB Output is correct
6 Correct 57 ms 3628 KB Output is correct
7 Correct 60 ms 3544 KB Output is correct
8 Correct 47 ms 7512 KB Output is correct
9 Correct 60 ms 3648 KB Output is correct
10 Correct 61 ms 3740 KB Output is correct
11 Correct 52 ms 7536 KB Output is correct
12 Execution timed out 2064 ms 10072 KB Time limit exceeded
13 Halted 0 ms 0 KB -