제출 #1069907

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1069907		vjudge1	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	1519 ms	126804 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;


#define ar array
#define ll long long
#define ld long double
#define sza(x) ((int)x.size())
#define all(a) (a).begin(), (a).end()

const int MAX_N = 2e6 + 5;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;
int n, m, cnt;
const char clist[4] = {'C','U','G','A'};

struct snode{
    char f, s;
    int ind;
};

struct node{
    int father , sz;
    vector<snode> child;
    node(){
        sz =0;
        cnt++;
    }
};
node v[MAX_N];
void addstring(string& s){
    int len = s.length();
    int curnode = 0;
    for (int i = 0;i<len;i++){
        //cout << curnode <<endl;
        int found = -1;
        for (auto k : v[curnode].child){
            if (k.f==s[i]&&k.s==s[len-i-1]){
                found = k.ind;
                break;
            }
        }
        if (found==-1){
            node newnode;
            newnode.father = curnode;
            v[curnode].child.push_back({s[i],s[len-i-1],cnt});
            v[cnt] = newnode;
            found = cnt;
        }
        curnode = found;
    }
    while (curnode != -1){
//cout << curnode <<" A"<<endl;
        v[curnode].sz++;
        curnode = v[curnode].father;
        //cout << curnode <<endl;
    }
}

int findstring(int i, int ptr, string& a, string& b, int& mx){
    if (ptr==mx) return v[i].sz;
    int ret = 0;
    if (a[ptr]=='0'){
        for (auto k : v[i].child)
            if (k.s==b[ptr]) ret += findstring(k.ind,ptr+1,a,b,mx);
        return ret;
    }
    if (b[ptr]=='0'){
        for (auto k : v[i].child)
            if (k.f==a[ptr]) ret += findstring(k.ind,ptr+1,a,b,mx);
        return ret;
    }
    //cout << b <<endl;
    for (auto k : v[i].child)
        if (k.f==a[ptr]&&k.s==b[ptr]) ret+= findstring(k.ind,ptr+1,a,b,mx);
    return ret;
}

void solve() {
    node newnode;
    cnt = 0;
    newnode.father = -1;
    v[0] = newnode;
    cin >> n >> m;
    string s, a, b;
    while (n--){
        cin >> s;
        addstring(s);
    }
    while (m--){
        cin >> a >> b;
        reverse(b.begin(),b.end());
        while (a.length()>b.length()) b.append("0");
        while (b.length()>a.length()) a.append("0");
        int mx = a.length();
        cout << findstring(0,0,a,b,mx)<<"\n";
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int tc = 1;
    // cin >> tc;
    for (int t = 1; t <= tc; t++) {
        // cout << "Case #" << t << ": ";
        solve();
    }
}

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