oj.uz

Submission #524535

# Submission time Handle Problem Language Result Execution time Memory
524535 2022-02-09T12:48:25 Z tato Trener (COCI20_trener) C++14
55 / 110
 2000 ms 436836 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(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.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 11 ms 2896 KB Output is correct
2 Correct 11 ms 3020 KB Output is correct
3 Correct 10 ms 2892 KB Output is correct
4 Correct 51 ms 7836 KB Output is correct
5 Correct 46 ms 3160 KB Output is correct
6 Correct 46 ms 3128 KB Output is correct
7 Correct 52 ms 7788 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 11 ms 2896 KB Output is correct
6 Correct 11 ms 3020 KB Output is correct
7 Correct 10 ms 2892 KB Output is correct
8 Correct 51 ms 7836 KB Output is correct
9 Correct 46 ms 3160 KB Output is correct
10 Correct 46 ms 3128 KB Output is correct
11 Correct 52 ms 7788 KB Output is correct
12 Correct 1103 ms 11484 KB Output is correct
13 Correct 1095 ms 13300 KB Output is correct
14 Correct 1090 ms 13300 KB Output is correct
15 Correct 1130 ms 13380 KB Output is correct
16 Execution timed out 2069 ms 436836 KB Time limit exceeded
17 Halted 0 ms 0 KB -