제출 #1277595

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277595		dosts	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	944 ms	843528 KiB

selling_rna

#include <bits/stdc++.h>
#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;

vector<vector<int>> ids,qshere;
vector<int> trieroot,v;
vector<array<int,4>> c;
int newnode() {
    trieroot.push_back(-1);
    v.push_back(0);
    c.push_back({-1,-1,-1,-1});
    ids.push_back({});
    qshere.push_back({});
    return id++;
}

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

void ins(int node,int id,const string& s,int qry,int dep) {
    v[node]++;
    if (dep == big(s)) {
        if (!qry) ids[node].push_back(id);
        else if (qry == 1) qshere[node].push_back(id);
        return;
    }
    char togo = s[dep];
    if (c[node][togo-'A'] == -1) c[node][togo-'A'] = newnode();
    ins(c[node][togo-'A'],id,s,qry,dep+1);
}


int query(int node,const string& s,int dep) {
    if (dep == big(s)) return v[node];
    int togo = s[dep];
    if (c[node][togo-'A'] == -1) return 0;
    return query(c[node][togo-'A'],s,dep+1);
}


void walk(int node) {
    for (auto it : ids[node]) {
        if (trieroot[node] == -1) trieroot[node] = newnode();
        ins(trieroot[node],it,rev[it],2,0);
    }
    for (int i = 0;i<4;i++) {
        if (c[node][i] == -1) continue;
        int it = c[node][i];
        walk(c[node][i]);
        if (big(ids[node]) < big(ids[it])) {
            ids[node].swap(ids[it]);
            swap(trieroot[node],trieroot[it]);
        }
        for (auto id : ids[it]) {
            if (trieroot[node] == -1) trieroot[node] = newnode();
            ins(trieroot[node],id,rev[id],2,0);
            ids[node].push_back(id);
        } 
        ids[it].clear();
    }
    for (auto it : qshere[node]) {
        if (trieroot[node] == -1) {
            ans[it] = 0;
            continue;
        }
        int qq = query(trieroot[node],qs[it].second,0);
        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]));
    }
    int root = newnode();
    for (int i=1;i<=n;i++) ins(root,i,strs[i],0,0);
    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';
        }
        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