Submission #849448

#	Time	Username	Problem	Language	Result	Execution time	Memory
849448		LeonaRaging	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	158 ms	98888 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb emplace_back
#define T pair<int,int>
#define SZ(val) (int)val.size()
#define all(val) val.begin(), val.end()
#define db(val) "[" #val " = " << (val) << "] "

const int maxn = 1e5 + 4;

struct Node {
	int nxt[4], id, cnt, leaf;
	Node() {
		memset(nxt, 0, sizeof nxt);
		id = cnt = leaf = 0;
	}
};

int n, q, num, res[maxn];
string a[maxn];
map<char,char> mp;
vector<Node> t(1);
vector<tuple<string,int,int>> que[maxn];

void add(string &s, int id = 0) {
	int v = 0;
	for (int i = 0; i < SZ(s); i++) {
		int c = s[i] - 'a';
		if (!t[v].nxt[c]) {
			t[v].nxt[c] = t.size();
			t.pb();
		}
		v = t[v].nxt[c];
		if (!t[v].id) t[v].id = id;
		t[v].cnt++;
	}
	t[v].leaf++;
}

T Find(string &s) {
	int v = 0;
	for (int i = 0; i < SZ(s); i++) {
		int c = s[i] - 'a';
		if (!t[v].nxt[c]) return {1, 0};
		v = t[v].nxt[c];
	}
	return {t[v].id, t[v].cnt};
}

void dfs(int v, string &s) {
	while (t[v].leaf--) a[++num] = s;
	for (int c = 0; c < 4; c++)
		if (t[v].nxt[c]) {
			s += char(c + 'a');
			dfs(t[v].nxt[c], s);
			s.pop_back();
		}
}

string Convert(string &s) {
	string t;
    for (int i = 0; i < SZ(s); i++)
    	t += mp[s[i]];
    return t;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> q;
    mp['A'] = 'a', mp['U'] = 'b', mp['G'] = 'c', mp['C'] = 'd';
    for (int i = 1; i <= n; i++) {
    	string s; cin >> s;
    	s = Convert(s);
    	add(s);
    }
    string s;
    dfs(0, s);
    vector<Node>(1).swap(t);
    for (int i = 1; i <= n; i++)
    	add(a[i], i);
    for (int i = 1; i <= q; i++) {
    	string u, v; cin >> u >> v;
    	u = Convert(u);
    	v = Convert(v);
    	T pos = Find(u);
    	que[pos.fi - 1].pb(v, i, -1);
    	que[pos.fi + pos.se - 1].pb(v, i, 1);
    }
    vector<Node>(1).swap(t);
    for (int i = 1; i <= n; i++) {
    	reverse(all(a[i])); add(a[i]);
    	for (auto it : que[i]) {
    		string s; int id, t; tie(s, id, t) = it;
    		reverse(all(s));
    		res[id] += t * Find(s).se;
    	}
    }
    for (int i = 1; i <= q; i++)
    	cout << res[i] << '\n';
}

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