oj.uz

Submission #102615

# Submission time Handle Problem Language Result Execution time Memory
102615 2019-03-26T09:28:05 Z Minnakhmetov Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 431 ms 146672 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 84088 KB Output is correct
2 Correct 72 ms 84088 KB Output is correct
3 Correct 78 ms 84088 KB Output is correct
4 Correct 73 ms 84216 KB Output is correct
5 Correct 71 ms 84088 KB Output is correct
6 Correct 84 ms 84136 KB Output is correct
7 Correct 76 ms 84104 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 134632 KB Output is correct
2 Correct 319 ms 136216 KB Output is correct
3 Correct 407 ms 146672 KB Output is correct
4 Correct 413 ms 145088 KB Output is correct
5 Correct 333 ms 122872 KB Output is correct
6 Correct 345 ms 123564 KB Output is correct
7 Correct 253 ms 119428 KB Output is correct
8 Correct 431 ms 139968 KB Output is correct
9 Correct 386 ms 138872 KB Output is correct
10 Correct 319 ms 136440 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 86568 KB Output is correct
2 Correct 91 ms 86484 KB Output is correct
3 Correct 99 ms 86768 KB Output is correct
4 Correct 85 ms 86520 KB Output is correct
5 Correct 94 ms 86508 KB Output is correct
6 Correct 101 ms 86624 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 84088 KB Output is correct
2 Correct 72 ms 84088 KB Output is correct
3 Correct 78 ms 84088 KB Output is correct
4 Correct 73 ms 84216 KB Output is correct
5 Correct 71 ms 84088 KB Output is correct
6 Correct 84 ms 84136 KB Output is correct
7 Correct 76 ms 84104 KB Output is correct
8 Correct 362 ms 134632 KB Output is correct
9 Correct 319 ms 136216 KB Output is correct
10 Correct 407 ms 146672 KB Output is correct
11 Correct 413 ms 145088 KB Output is correct
12 Correct 333 ms 122872 KB Output is correct
13 Correct 345 ms 123564 KB Output is correct
14 Correct 253 ms 119428 KB Output is correct
15 Correct 431 ms 139968 KB Output is correct
16 Correct 386 ms 138872 KB Output is correct
17 Correct 319 ms 136440 KB Output is correct
18 Correct 104 ms 86568 KB Output is correct
19 Correct 91 ms 86484 KB Output is correct
20 Correct 99 ms 86768 KB Output is correct
21 Correct 85 ms 86520 KB Output is correct
22 Correct 94 ms 86508 KB Output is correct
23 Correct 101 ms 86624 KB Output is correct
24 Correct 323 ms 132852 KB Output is correct
25 Correct 365 ms 133740 KB Output is correct
26 Correct 368 ms 133172 KB Output is correct
27 Correct 416 ms 141540 KB Output is correct
28 Correct 380 ms 131920 KB Output is correct
29 Correct 187 ms 104280 KB Output is correct