Submission #1277541

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277541		dosts	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	900 ms	810140 KiB

selling_rna

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;

const int N = 1e5+1;


int id = 0;

struct Node {
    int v = 0;
    vector<int> ids;
    vector<int> qshere;
    int trieroot;
    int c[4];
    Node() {
        c[0] = c[1] = c[2] = c[3] = trieroot = -1;
    };
};

vector<Node> nds;
int newnode() {
    nds.push_back(Node());
    return id++;
}

vector<string> strs(N),rev(N);
vector<pair<string,string>> qs(N);
vi ans(N);

void ins(int node,int id,const string& s,int qry = 0,int dep = 0) {
    //cerr << node sp id sp s sp qry sp dep << endl;
    nds[node].v++;
    if (dep == big(s)) {
        if (!qry) nds[node].ids.push_back(id);
        else if (qry == 1) nds[node].qshere.push_back(id);
        return;
    }
    char togo = s[dep];
    if (nds[node].c[togo-'A'] == -1) {
        nds[node].c[togo-'A'] = newnode();
        //cerr << "CHILD OF" sp node sp togo sp "BECAME " << nds[node].c[togo-'A'] << endl;
    }
    ins(nds[node].c[togo-'A'],id,s,qry,dep+1);
}


int query(int node,const string& s,int dep = 0) {
    //cerr << node sp s sp dep sp nds[node].v << endl;
    if (dep == big(s)) {
        return nds[node].v;
    }
    int togo = s[dep];
    if (nds[node].c[togo-'A'] == -1) return 0;
    return query(nds[node].c[togo-'A'],s,dep+1);
}
void walk(int node) {
    for (auto it : nds[node].ids) {
        if (nds[node].trieroot == -1) {
            nds[node].trieroot = newnode();
            //cerr << "ROOT OF" sp node sp "BECAME" sp nds[node].trieroot << endl;
        }
        ins(nds[node].trieroot,it,rev[it],2,0);
    }
    for (int i = 0;i<4;i++) {
        if (nds[node].c[i] == -1) continue;
        int it = nds[node].c[i];
        walk(nds[node].c[i]);
        if (big(nds[node].ids) < big(nds[it].ids)) {
            nds[node].ids.swap(nds[it].ids);
            swap(nds[node].trieroot,nds[it].trieroot);
        }
        for (auto id : nds[it].ids) {
            if (nds[node].trieroot == -1) {
                nds[node].trieroot = newnode();
                //cerr << "ROOT OF" sp node sp "BECAME" sp nds[node].trieroot << endl;
            }
            ins(nds[node].trieroot,id,rev[id],2,0);
            nds[node].ids.push_back(id);
        } 
    }
    for (auto it : nds[node].qshere) {
        if (nds[node].trieroot == -1) {
            ans[it] = 0;
            continue;
        }
        int qq = query(nds[node].trieroot,qs[it].second);
        //cout << node sp it sp qq << endl;
        ans[it] = qq;
    }
}

void solve() {
    int n,q;
    cin >> n >> q;
    for (int i=1;i<=n;i++) {
        cin >> strs[i];
        for (auto& c : strs[i]) {
            if (c == 'A' || c == 'C') continue;
            if (c == 'G') c = 'B';
            else c = 'D';
        }
        rev[i] = strs[i];
        reverse(all(rev[i]));
    }
    //for (int i=1;i<=n;i++) cout << strs[i] << endl;
    int root = newnode();
    for (int i=1;i<=n;i++) ins(root,i,strs[i]);
    for (int i = 1;i<=q;i++) {
        cin >> qs[i].ff >> qs[i].ss;
        reverse(all(qs[i].ss));
        for (auto& c : qs[i].ff) {
            if (c == 'A' || c == 'C') continue;
            if (c == 'G') c = 'B';
            else c = 'D';
        }
        for (auto& c : qs[i].ss) {
            if (c == 'A' || c == 'C') continue;
            if (c == 'G') c = 'B';
            else c = 'D';
        }
        //cout << qs[i].ff sp qs[i].ss << endl;
        ins(root,i,qs[i].ff,1,0);
    }
    walk(root);
    for (int i=1;i<=q;i++) cout << ans[i] << '\n';
} 

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef Dodi
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

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