oj.uz

답안 #522804

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
522804 2022-02-05T23:32:51 Z thiago_bastos Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1231 ms 200404 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 = 1e9 + 9, base = 1845;

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

int t[N][4], nos = 1;
unordered_map<int, int> cnt[N];
vector<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(int 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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8140 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 6 ms 8152 KB Output is correct
4 Correct 7 ms 8088 KB Output is correct
5 Correct 5 ms 8144 KB Output is correct
6 Correct 5 ms 8140 KB Output is correct
7 Correct 5 ms 8140 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1231 ms 184848 KB Output is correct
2 Correct 1217 ms 200404 KB Output is correct
3 Runtime error 26 ms 28536 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 9224 KB Output is correct
2 Correct 22 ms 9556 KB Output is correct
3 Correct 25 ms 9296 KB Output is correct
4 Correct 20 ms 8680 KB Output is correct
5 Correct 28 ms 9292 KB Output is correct
6 Correct 24 ms 9324 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8140 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 6 ms 8152 KB Output is correct
4 Correct 7 ms 8088 KB Output is correct
5 Correct 5 ms 8144 KB Output is correct
6 Correct 5 ms 8140 KB Output is correct
7 Correct 5 ms 8140 KB Output is correct
8 Correct 1231 ms 184848 KB Output is correct
9 Correct 1217 ms 200404 KB Output is correct
10 Runtime error 26 ms 28536 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -