oj.uz

Submission #522803

# Submission time Handle Problem Language Result Execution time Memory
522803 2022-02-05T23:28:42 Z thiago_bastos Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 246704 KB 
#include "bits/stdc++.h"

using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using i32 = int;
using u32 = unsigned;
using i16 = short;
using u16 = unsigned short;
using ld = long double;
using ii = pair<int, int>;

const int N = 1e5, mod[] = {int(1e9 + 7), int(1e9 + 9)}, base[] = {1845, 1791};

vector<ii> h(string& s) {
	int n = s.size();
	vector<ii> a(n + 1);
	i64 k1 = 1, k2 = 1;
	a[0] = {0, 0};
	for(int i = 1; i <= n; ++i) {
		auto  [x0, y0] = a[i - 1];
		auto& [x1, y1] = a[i];
		k1 = k1 * base[0] % mod[0];
		k2 = k2 * base[1] % mod[1];
		x1 = (x0 + (s[i - 1] - '0' + 1) * k1) % mod[0];
		y1 = (y0 + (s[i - 1] - '0' + 1) * k2) % mod[1];
	}
	a.erase(a.begin());
	return a;
}

int t[N][4], nos = 1;
map<ii, int> cnt[N];
vector<pair<int, ii>> query[N];
vector<int> ans;

void push(string& s) {
	int i = 0;
	for(char ch : s) {
		int& k = t[i][ch - '0'];
		if(k < 0) {
			memset(t[nos], -1, sizeof(t[nos]));
			k = nos++;
		}
		i = k;
	}
	reverse(s.begin(), s.end());
	for(ii y : h(s)) ++cnt[i][y];
}

void f(string& s) {
	string alpha = "AGCU";
	for(char& ch : s) {
		for(int i = 0; i < 4; ++i) {
			if(ch == alpha[i]) {
				ch = i + '0';
				break;
			}
		}
	}
}

void dfs(int u) {
	for(int v = 0; v < 4; ++v) {
		int z = t[u][v];
		if(z < 0) continue;
		dfs(z);
		if(cnt[z].size() > cnt[u].size()) swap(cnt[u], cnt[z]);
		for(auto [x, y] : cnt[z]) cnt[u][x] += y;
	}
	for(auto [pos, ht] : query[u]) {
		auto it = cnt[u].find(ht);
		if(it == cnt[u].end()) continue;
		ans[pos] += it->second;
	}
}

void solve() {
	
	int n, m;

	cin >> n >> m;

	memset(t[0], -1, sizeof(t[0]));
	ans.assign(m, 0);

	for(int i = 0; i < n; ++i) {
		string s;
		cin >> s;
		f(s);
		push(s);
	}

	for(int i = 0; i < m; ++i) {
		string a, b;
		int k = 0;
		cin >> a >> b;
		f(a);
		f(b);
		reverse(b.begin(), b.end());
		for(char ch : a) {
			if(t[k][ch - '0'] < 0) {
				k = -1;
				break;
			}
			k = t[k][ch - '0'];
		}
		if(k < 0) continue;
		query[k].emplace_back(i, h(b).back());
	}

	dfs(0);

	for(int k : ans) cout << k << '\n';
}
	

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) solve();
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 4 ms 7308 KB Output is correct
5 Correct 4 ms 7328 KB Output is correct
6 Correct 5 ms 7364 KB Output is correct
7 Correct 4 ms 7368 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 9032 KB Output is correct
2 Correct 25 ms 9724 KB Output is correct
3 Correct 25 ms 9308 KB Output is correct
4 Correct 19 ms 8528 KB Output is correct
5 Correct 24 ms 9284 KB Output is correct
6 Correct 26 ms 9208 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 4 ms 7308 KB Output is correct
5 Correct 4 ms 7328 KB Output is correct
6 Correct 5 ms 7364 KB Output is correct
7 Correct 4 ms 7368 KB Output is correct
8 Execution timed out 1569 ms 246704 KB Time limit exceeded
9 Halted 0 ms 0 KB -