Submission #1267516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267516		nlsosad	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	226 ms	264888 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
string a[100001], p[100001], q[100001], ra[100001];
int res[100001];

vector<int> tv[1000002], luu[1000002];
int sum[1000002];
int idx[26];

struct trie{
	struct node{
		int nxt[4];
		int cnt;
		node(){
			nxt[0] = nxt[1]=nxt[2] = nxt[3] = 0;
			cnt = 0;
		}
	};
	vector<node> tr;
	int lst = 1;
	void init(){
		tr.resize(1);
	}
	void add(string &s, int tro){
		int moc = 0;
		for (char i:s){
			int id = idx[i-'A'];
			if(tr[moc].nxt[id]==0){
				node tmp;
				tr.push_back(tmp);
				tr[moc].nxt[id] = lst;
				moc = lst;
				lst++;
			}else{
				moc = tr[moc].nxt[id];
			}
			tr[moc].cnt++;
		}
		if(tro!=-1){
			tv[moc].push_back(tro);
		}
	}
	
	void cook(string &s, int tro){
		int moc = 0;
		for (char i:s){
			int id = idx[i-'A'];
			if(tr[moc].nxt[id]==0)break;
			moc = tr[moc].nxt[id];
		}
		if(moc==0)return;
		luu[moc].push_back(tro);
		sum[moc] += a[tro].size();
	}
	int count(string &s){
		int moc = 0;
		for (char i:s){
			int id = idx[i-'A'];
			moc = tr[moc].nxt[id];
			if(moc==0)return 0;
		}
		return tr[moc].cnt;
	}
};

trie con[1000002];
trie cay;

void dfs(int u){
	for (int i = 0;i<4;++i){
		if(cay.tr[u].nxt[i]!=0){
			dfs(cay.tr[u].nxt[i]);
			int v = cay.tr[u].nxt[i];
			if(sum[u] < sum[v]){
				swap(con[u], con[v]);
				swap(sum[u], sum[v]);
				swap(luu[u], luu[v]);
			}
			for (int j:luu[v]){
				con[u].add(ra[j], -1);
				luu[u].push_back(j);
			}
			sum[u] += sum[v];
		}
	}
	for (int i:tv[u]){
		res[i] = con[u].count(q[i]);
		// cout << u << ' ' << i << ' ' << q[i] << " NGU\n";
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n>> m;
	for (int i = 1;i<=n;++i){
		cin >> a[i];
		ra[i] = a[i];
		reverse(ra[i].begin(), ra[i].end());
	}
	idx['A'-'A'] = 0;
	idx['C'-'A'] = 1;
	idx['G'-'A'] = 2;
	idx['U'-'A'] = 3;
	cay.init();
	for (int i = 1;i<=m;++i){
		cin >> p[i] >> q[i];
		reverse(q[i].begin(), q[i].end());
		cay.add(p[i], i);
	}
	for (int i = 1;i<=n;++i){
		cay.cook(a[i], i);
	}
	int lst = cay.lst;
	// cout << lst << '\n';
	for (int i = 0;i<lst;++i){
		con[i].init();
		for (int j:luu[i]){
			con[i].add(ra[j], -1);
		}
	}
	// cout << q[3];return 0;
	// cout << con[3].lst;return 0;
	// cout << luu[3].size();return 0;
	// cout << con[3].count(q[3]);return 0;
	dfs(0);
	for (int i = 1;i<=m;++i){
		cout << res[i] << '\n';
	}
}

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