Submission #282624

#	Time	Username	Problem	Language	Result	Execution time	Memory
282624		limabeans	Selling RNA Strands (JOI16_selling_rna)	C++17	10 / 100	1591 ms	748892 KiB

selling_rna

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll mod = 1e9+7;
const int maxn = 1e6 + 5;


int n, m;
string s[maxn];

struct node {
    set<int> inds;
    node *ch[26];
    node() {
	for (int i=0; i<26; i++) {
	    ch[i]=NULL;
	}
    }
};


node *trie;
node *rtrie;


void insert(int i, const string& s, node *cur) {
    cur->inds.insert(i);
    
    for (char c: s) {
	if (cur->ch[c-'A'] == NULL) {
	    cur->ch[c-'A'] = new node();
	}
	cur = cur->ch[c-'A'];
	cur->inds.insert(i);
    }
}


set<int> walk(const string& s, node *cur) {
    for (char c: s) {
	if (cur->ch[c-'A']==NULL) return {};
	cur = cur->ch[c-'A'];
    }

    return cur->inds;
}
    


int solve(string p, string q) {
    set<int> L = walk(p, trie);
    reverse(q.begin(), q.end());
    set<int> R = walk(q, rtrie);
    int res = 0;
    for (int i: L) {
	if (R.count(i)) res++;
    }
    return res;
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>m;
    trie = new node();
    rtrie = new node();
    
    for (int i=0; i<n; i++) {
	cin>>s[i];
	insert(i, s[i], trie);
	string rs = s[i];
	reverse(rs.begin(),rs.end());
	insert(i, rs, rtrie);
    }

    for (int i=0; i<m; i++) {
	string p, q;
	cin>>p>>q;
	cout<<solve(p,q)<<"\n";
    }
    
    
    return 0;
}

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