제출 #89702

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
89702		mra2322001	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	539 ms	187756 KiB

selling_rna

/*
    Bai nay ta khong can co dinh 2 vi tri, ta chi can co dinh 1 vi tri la du, vi tri con lai dung dem
    --> rut ra: co bai ta can co dinh nhieu thuws thi thuwr coos dinhj 1 cais rooif cais kia dungf cachs naof
    ddeer nos bieens maats ddi laf dduowcj
*/
#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i < (n); i++)
#define f1(i, n) for(int i(1); i <= n; i++)

using namespace std;
typedef long long ll;
const int N = 100002;

int id(char x){
    if(x=='A') return 0;
    if(x=='G') return 1;
    if(x=='C') return 2;
    if(x=='U') return 3;
}

int t1[2000002][4], t2[2000002][4], cnt1 = 1, cnt2 = 1, cnt = 0, low[N*20], high[N*20];
int n, q;
string s[N];
vector <vector <int> > v;

void add2(string cur){
    int len = cur.size();
    int u = 1;
    f0(i, len){
        char now = cur[i];
        if(t2[u][id(now)]==0){
            t2[u][id(now)] = ++cnt2;
        }
        u = t2[u][id(now)];
    }
}

void add1(string cur, int e){
    int len = cur.size();
    int u = 1;
    f0(i, len){
        char now = cur[i];
        if(t1[u][id(now)]==0){
            t1[u][id(now)] = ++cnt1;
        }
        u = t1[u][id(now)];
        v[u].emplace_back(e);
    }
}

void dfs(int u, int p){
    low[u] = ++cnt;
    f0(i, 4){
        if(t2[u][i]==0) continue;
        dfs(t2[u][i], u);
    }
    high[u] = ++cnt;
}

int get_low(string cur){
    int len = cur.size();
    int u = 1;
    f0(i, len){
        u = t2[u][id(cur[i])];
    }
    return low[u];
}

int find1(string cur){
    int len = cur.size();
    int u = 1;
    f0(i, len){
        if(t1[u][id(cur[i])]==0) return 0;
        u = t1[u][id(cur[i])];
    }
    return u;
}

pair <int, int> find2(string cur){
    int len = cur.size();
    int u = 1;
    f0(i, len){
        if(t2[u][id(cur[i])]==0) return {-1, -1};
        u = t2[u][id(cur[i])];
    }
    return {low[u], high[u]};
}

int main(){
    ios_base::sync_with_stdio(0);

    cin >> n >> q;
    int dem = 0;
    f1(i, n){
        cin >> s[i];
        dem += s[i].size();
        reverse(s[i].begin(), s[i].end());
        add2(s[i]);
    }
    v.resize(dem + 1);
    dfs(1, 1);
    f1(i, n){
        int now = get_low(s[i]);
        reverse(s[i].begin(), s[i].end());
        add1(s[i], now);
    }
    f1(i, cnt1) sort(v[i].begin(), v[i].end());
    while(q--){
        string s1, s2;
        cin >> s1;
        cin >> s2;
        reverse(s2.begin(), s2.end());
        int g1 = find1(s1);
        pair <int, int> cur = find2(s2);
        if(g1==0 || cur.first==-1){
            cout << 0 << "\n";
            continue;
        }
        int k1 = lower_bound(v[g1].begin(), v[g1].end(), cur.first) - v[g1].begin();
        int k2 = upper_bound(v[g1].begin(), v[g1].end(), cur.second) - v[g1].begin() - 1;
        int res = k2 - k1 + 1;
        res = max(res, 0);
        cout << res << "\n";
    }
}

컴파일 시 표준 에러 (stderr) 메시지

selling_rna.cpp: In function 'int id(char)':
selling_rna.cpp:19:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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