제출 #1031509

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

selling_rna

#include<bits/stdc++.h>
using namespace std;
#define N 1<<23
int rts[N],ch1[N][4],ch2[N][4],mmpp[128],CC1,CC2,rt,sz[N],val[N],ans[200100];
bitset<N> hasaQ;
map<int,vector<pair<vector<int>,int>>> qrs;
int a_node(string str){
    vector<int>v;
    for(auto i:str)
        v.push_back(mmpp[i]);
    int k=rt;
    for(auto i:v){
        if(!ch1[k][i])
            ch1[k][i]=++CC1;
        k=ch1[k][i];
    }
    return k;
}
void Adtri2(int nod,string str,int b=1){
    vector<int>v;
    for(auto i:str)
        v.push_back(mmpp[i]);
    if(!rts[nod])
        rts[nod]=++CC2;
    int k=rts[nod];
    sz[nod]+=str.size();
    for(auto i:v){
        if(!ch2[k][i])
            ch2[k][i]=++CC2;
        k=ch2[k][i],val[k]+=b;
    }
    sz[k]+=b;
}
int mrg(int a,int b){
    if(!a||!b)return a+b;
    if(sz[b]>sz[a])swap(a,b);
    sz[a]+=sz[b],val[a]+=val[b];
    for(int i=0;i<4;i++)
        ch2[a][i]=mrg(ch2[a][i],ch2[b][i]);
    return a;
}
int gothrough(int n,vector<int>v){
    for(auto i:v)
        n=ch2[n][i];
    return n;
}
void do_a_dfs(int n){
    if(!n)return;
    for(auto k:ch1[n])
        do_a_dfs(k),rts[n]=mrg(rts[n],rts[k]);
    if(hasaQ[n]){
        for(auto [x,y]:qrs[n])
            ans[y]+=val[gothrough(rts[n],x)];
    }
}
int main(){
    mmpp['A']=0;
    mmpp['C']=rt=CC1=1;
    mmpp['G']=2;
    mmpp['U']=3;
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        string str;
        cin>>str;
        int k=a_node(str);
        reverse(str.begin(),str.end());
        Adtri2(k,str);
    }
    for(int i=0;i<m;i++){
        string a,b;
        cin>>a>>b;
        reverse(b.begin(),b.end());
        int k=a_node(a);
        vector<int>v;
        for(auto i:b)
            v.push_back(mmpp[i]);
        hasaQ[k]=1;
        qrs[k].push_back({v,i});
    }
    for(int x=CC2;x;x--) {
        sz[x]=1;
        for(auto k:ch2[x])
            sz[x]+=sz[k];
    }
    do_a_dfs(rt);
    for(int i=0;i<m;i++)
        cout<<ans[i]<<'\n';
}

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

selling_rna.cpp: In function 'int a_node(std::string)':
selling_rna.cpp:10:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   10 |         v.push_back(mmpp[i]);
      |                          ^
selling_rna.cpp: In function 'void Adtri2(int, std::string, int)':
selling_rna.cpp:22:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   22 |         v.push_back(mmpp[i]);
      |                          ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:77:30: warning: array subscript has type 'char' [-Wchar-subscripts]
   77 |             v.push_back(mmpp[i]);
      |                              ^

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