Submission #342792

#	Time	Username	Problem	Language	Result	Execution time	Memory
342792		Nursik	Selling RNA Strands (JOI16_selling_rna)	C++14	10 / 100	1622 ms	553780 KiB

selling_rna

#include <bits/stdc++.h>
          
#define fi first
#define se second
#define pp pop_back
#define ll long long
#define pb push_back
#define ld long double
#define debug cout << "OK\n";
#define all(x) x.begin(), x.end() 
#define mp make_pair 
using namespace std;        
 
const ll N = 1e6;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll pe = mod2; 
const ll pe2 = 570210983;
const ld eps = 1e-6; 
 
 
/*
Rucode: jaqVYNrpMj
JUDGE_ID: 295965SY
dl:160532
*/
void data() {
	#ifdef NURS
        freopen("main.in", "r", stdin);
        freopen("main.out", "w", stdout);
    #endif	
} 

int n, m;
string s[N], l[N], r[N]; ll hashl[N], hashr[N], hashl2[N], hashr2[N];
map<string, int> was, was2, used, used2;
map<string, int> hsh, hsh2;
vector<int> g[N];
map<pair<string, string>, int> add;
string now = "";
map<int, string> hashw;
void dfs(int v, int len, int p)
{
	if (len == 2)
	{
		add[{now, hashw[v]}]++; 
	}
	for (int i = 0; i < g[v].size(); i++)
	{
		int to = g[v][i];
		if (len + 1 <= 2 && to != p)
			dfs(to, len + 1, v);
	}
}
main()
{
	data();
	ios_base::sync_with_stdio(0),
	cin.tie(0),cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> s[i];

	for (int i = 1; i <= m; i++)
	{
		cin >> l[i] >> r[i];
		was[l[i]] = 1, was2[r[i]] = 1;	
	}
	//хеширую
	for (int i = 1; i <= m; i++)
	{
		ll hash = 0;
		for (int j = 0; j < l[i].size(); j++)
			hash = hash * pe % mod + (l[i][j] - 'A' + 1), hash = hash % mod;		
		
		hashl[i] = hash;
		hashl2[i] = hash;
		hash = 0;
		for (int j = 0; j < r[i].size(); j++)
			hash = hash * pe % mod + (r[i][j] - 'A' + 1), hash = hash % mod;
		
		hashr[i] = hash;
		hashr2[i] = hash;
	}
	//просто сжатие хешей
	sort(hashl2 + 1, hashl2 + m + 1);
	sort(hashr2 + 1, hashr2 + m + 1);
	int sz = unique(hashl2 + 1, hashl2 + m + 1) - hashl2 - 1;
	int sz2 = unique(hashr2 + 1, hashr2 + m + 1) - hashr2 - 1;
	for (int i = 1; i <= m; i++)
	{
		hashl[i] = lower_bound(hashl2 + 1, hashl2 + sz + 1, hashl[i]) - hashl2;
		hashr[i] = lower_bound(hashr2 + 1, hashr2 + sz2 + 1, hashr[i]) - hashr2;
		hsh[l[i]] = hashl[i];
		hsh2[r[i]] = hashr[i];
		hashw[hsh[l[i]] + 9 * n] = l[i];
	}	
	//добавил ребра
	for (int i = 1; i <= n; i++)
	{
		string q = "";
		for (int j = 0; j < s[i].size(); j++)
		{
			q += s[i][j];
			if (was[q])
			{
				g[i].pb(hsh[q] + 9 * n), g[hsh[q] + 9 * n].pb(i);	
			//	cout << hsh[q] + 9 * n << " " << i  << '\n';
			//	cout << i  << " " << hsh[q] + 9 * n << '\n';
			}
		}
		q = "";
		for (int j = s[i].size() - 1; j >= 0; j--)
		{
			q = s[i][j] + q;
			if (was2[q])
			{
				g[i].pb(hsh2[q] + 4 * n), g[hsh2[q] + 4 * n].pb(i);
			//	cout << i + n << " " << hsh2[q] + 4 * n << '\n';
			//	cout << hsh2[q] + n * 4 << " " << i + n << '\n';
			}
		}
	}
	//end
	for (int i = 1; i <= m; i++)
	{
		if (!used2[r[i]] && hsh2[r[i]] > 0)
		{
			now = r[i];	 
			dfs(hsh2[r[i]] + 4 * n, 0, 0);
			used2[r[i]] = 1;
		}
		cout << add[{r[i], l[i]}] << '\n';	
	}
}

Compilation message (stderr)

selling_rna.cpp: In function 'void dfs(int, int, int)':
selling_rna.cpp:48:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for (int i = 0; i < g[v].size(); i++)
      |                  ~~^~~~~~~~~~~~~
selling_rna.cpp: At global scope:
selling_rna.cpp:55:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   55 | main()
      |      ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:73:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |   for (int j = 0; j < l[i].size(); j++)
      |                   ~~^~~~~~~~~~~~~
selling_rna.cpp:79:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   for (int j = 0; j < r[i].size(); j++)
      |                   ~~^~~~~~~~~~~~~
selling_rna.cpp:102:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |   for (int j = 0; j < s[i].size(); j++)
      |                   ~~^~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40