oj.uz

Submission #282624

# Submission time Handle Problem Language Result Execution time Memory
282624 2020-08-24T16:11:29 Z limabeans Selling RNA Strands (JOI16_selling_rna) C++17
10 / 100
 1500 ms 748892 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31744 KB Output is correct
2 Correct 19 ms 31744 KB Output is correct
3 Correct 20 ms 31744 KB Output is correct
4 Correct 20 ms 31744 KB Output is correct
5 Correct 19 ms 31744 KB Output is correct
6 Correct 19 ms 31744 KB Output is correct
7 Correct 19 ms 31708 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31744 KB Output is correct
2 Correct 19 ms 31744 KB Output is correct
3 Correct 20 ms 31744 KB Output is correct
4 Correct 20 ms 31744 KB Output is correct
5 Correct 19 ms 31744 KB Output is correct
6 Correct 19 ms 31744 KB Output is correct
7 Correct 19 ms 31708 KB Output is correct
8 Execution timed out 1563 ms 748892 KB Time limit exceeded
9 Halted 0 ms 0 KB -