Submission #102615

#	Time	Username	Problem	Language	Result	Execution time	Memory
102615		Minnakhmetov	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	431 ms	146672 KiB

selling_rna

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
#pragma warning(disable : 4996)

const int P = 5, N = 1e5 + 5, L = 2e6 + 5, A = 4;
int ind[N];
vector<pair<ll, int>> ga[N];
int to[L][A], lb[L], rb[L];
vector<int> en[L];
string s[N];
int z = 1, timer = 0;

void dfs(int node) {
	lb[node] = ++timer;
	for (int i : en[node]) {
		ll h = 0;
		for (int j = 0; j < s[i].size(); j++) {
			h = h * P + s[i][j];
			ga[j + 1].push_back({ h, lb[node] });
		}
	}
	for (int i = 0; i < A; i++) {
		if (to[node][i] != -1) {
			dfs(to[node][i]);
			rb[node] = rb[to[node][i]];
		}
	}
	rb[node] = timer;
}

signed main() {
#ifdef HOME
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n, m;
	cin >> n >> m;
	
	ind['A'] = 0;
	ind['G'] = 1;
	ind['C'] = 2;
	ind['U'] = 3;

	memset(to, -1, sizeof(to));

	for (int i = 0; i < n; i++) {
		cin >> s[i];
		int v = 0;
		for (int j = 0; j < s[i].size(); j++) {
			s[i][j] = ind[s[i][j]];
			int c = s[i][j];
			if (to[v][c] == -1) {
				to[v][c] = z++;
			}
			v = to[v][c];
		}
		en[v].push_back(i);
		reverse(all(s[i]));
	}

	dfs(0);

	for (int i = 0; i < N; i++)
		sort(all(ga[i]));

	for (int i = 0; i < m; i++) {
		string p, q;
		cin >> p >> q;
		reverse(all(q));

		ll h = 0;
		for (char c : q)
			h = h * P + ind[c];

		int v = 0;
		bool ok = true;
		for (int j = 0; j < p.size(); j++) {
			int c = ind[p[j]];
			if (to[v][c] == -1) {
				ok = false;
				break;
			}
			v = to[v][c];
		}
		int ans = 0;
		if (ok) {
			ans = upper_bound(all(ga[q.size()]), make_pair(h, rb[v])) - 
				lower_bound(all(ga[q.size()]), make_pair(h, lb[v]));
		}
		cout << ans << "\n";
	}

	
	return 0;
}

Compilation message (stderr)

selling_rna.cpp:41:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable : 4996)
 
selling_rna.cpp: In function 'void dfs(int)':
selling_rna.cpp:55:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < s[i].size(); j++) {
                   ~~^~~~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:90:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < s[i].size(); j++) {
                   ~~^~~~~~~~~~~~~
selling_rna.cpp:91:25: warning: array subscript has type 'char' [-Wchar-subscripts]
    s[i][j] = ind[s[i][j]];
                         ^
selling_rna.cpp:114:21: warning: array subscript has type 'char' [-Wchar-subscripts]
    h = h * P + ind[c];
                     ^
selling_rna.cpp:118:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < p.size(); j++) {
                   ~~^~~~~~~~~~
selling_rna.cpp:119:20: warning: array subscript has type 'char' [-Wchar-subscripts]
    int c = ind[p[j]];
                    ^

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