oj.uz

Submission #102612

# Submission time Handle Problem Language Result Execution time Memory
102612 2019-03-26T09:18:34 Z Minnakhmetov Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 205172 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;
map<char, int> mp_ind = { {'A', 0}, {'U', 1}, {'G', 2}, {'C', 3} };
map<ll, vector<int>> mp_h[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];
			mp_h[j + 1][h].push_back(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;

	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] = mp_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 < m; i++) {
		string p, q;
		cin >> p >> q;
		reverse(all(q));

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

		int v = 0;
		bool ok = true;
		for (int j = 0; j < p.size(); j++) {
			int c = mp_ind[p[j]];
			if (to[v][c] == -1) {
				ok = false;
				break;
			}
			v = to[v][c];
		}
		int ans = 0;
		if (ok) {
			ans = upper_bound(all(mp_h[q.size()][h]), rb[v]) - lower_bound(all(mp_h[q.size()][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:85:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < s[i].size(); j++) {
                   ~~^~~~~~~~~~~~~
selling_rna.cpp:110:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < p.size(); j++) {
                   ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 86520 KB Output is correct
2 Correct 76 ms 86392 KB Output is correct
3 Correct 81 ms 86520 KB Output is correct
4 Correct 85 ms 86492 KB Output is correct
5 Correct 74 ms 86420 KB Output is correct
6 Correct 73 ms 86492 KB Output is correct
7 Correct 80 ms 86520 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1564 ms 205172 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 87540 KB Output is correct
2 Correct 98 ms 87844 KB Output is correct
3 Correct 105 ms 87668 KB Output is correct
4 Correct 108 ms 87468 KB Output is correct
5 Correct 96 ms 87416 KB Output is correct
6 Correct 100 ms 87544 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 86520 KB Output is correct
2 Correct 76 ms 86392 KB Output is correct
3 Correct 81 ms 86520 KB Output is correct
4 Correct 85 ms 86492 KB Output is correct
5 Correct 74 ms 86420 KB Output is correct
6 Correct 73 ms 86492 KB Output is correct
7 Correct 80 ms 86520 KB Output is correct
8 Execution timed out 1564 ms 205172 KB Time limit exceeded
9 Halted 0 ms 0 KB -