Submission #1025014

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025014		_8_8_	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	1538 ms	621396 KiB

selling_rna

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
const int  N = 2e6 + 20, MOD = (int)1e9+7;
 
struct node{
    node *next[26];
    int tin,tout;
    vector<int> id;
    node(){
        tin = 0,tout = 0;
        for(int i = 0;i < 26;i++){
            next[i] = nullptr;
        }
    }
};

node *p = new node(),*s = new node();
using pnode = node *;
int sp = 0,ss = 0;
int n,q;
void add(pnode v,string &x,int j){
    for(int i = 0;i < (int)x.size();i++){
        if(!v->next[(x[i] - 'A')]){
            v->next[(x[i] - 'A')] = new node();
        }
        v = v->next[(x[i] - 'A')];
    }
    v->id.push_back(j);
}
int timer = 0;
array<int,2> pt[N];
void dfs(pnode v){
    v->tin = ++timer;
    for(int k:v->id){
        if(pt[k][0] == -1){
            pt[k][0] = timer;
        }else{
            pt[k][1] = timer;
        }
    }
    for(int t = 0;t < 26;t++){
        if(v->next[t]){
            dfs(v->next[t]);
        }
    }
    v->tout = ++timer;
}
pair<int,int> get_tin(pnode v,string &x){
    for(int i = 0;i < (int)x.size();i++){
        if(v->next[(x[i] - 'A')]){
            v = v->next[(x[i] - 'A')];
        }else return {-1,-1};
    }
    return {v->tin,v->tout};
}
void test(){
    cin >> n >> q;
    for(int i = 1;i <= n;i++){
        string t;
        cin >> t;
        add(p,t,i);
        reverse(t.begin(),t.end());
        add(s,t,i);
        pt[i] = {-1,-1};
    }
    dfs(p);
    timer = 0;
    dfs(s);
    for(int i = 0;i < q;i++){
        string x,y;
        cin >> x >> y;
        reverse(y.begin(),y.end());
        pair<int,int> ti = get_tin(p,x),to = get_tin(s,y);
        // cout << ti.first << ' ' <<ti.second << ' ' << to.first << ' ' <<to.second << '\n';
        if(ti.first == 0 || to.first == 0){
            cout << 0 << '\n';continue;
        }
        int c = 0;
        for(int j = 1;j <= n;j++){
            if(pt[j][0] >= ti.first && pt[j][0] <= ti.second && pt[j][1] >=to.first && pt[j][1] <= to.second){
                c++;
            }
        }
        cout << c << '\n';
    }
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--){
        test();
    }
}

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