제출 #399242

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

selling_rna

#include <bits/stdc++.h>

using namespace std;

int index(char c){
    if(c == 'A') return 0;
    if(c == 'G') return 1;
    if(c == 'C') return 2;
    return 3;
}

struct trie{
    vector<vector<int>> t;
    vector<vector<int>> inds;

    int uj_pont(){
        t.push_back(vector<int>(4, -1));
        inds.push_back(vector<int>());
        return (int)t.size()-1;
    }

    void init(){
        uj_pont();
    }

    int add(string s, int ind){
        int x = 0;
        for(char &c : s){
            int y = index(c);
            if(t[x][y] == -1)
                t[x][y] = uj_pont();
            x = t[x][y];
        }
        inds[x].push_back(ind);
        return x;
    }
};

vector<vector<int>> query;
vector<int> ert, veg, ki;
vector<string> vs;
trie t1, t2;

void add(trie &t, string s){
    int x = 0;
    for(char &c : s){
        ert[x]++;
        int y = index(c);
        if(t.t[x][y] == -1)
            return;
        x = t.t[x][y];
    }
    ert[x]++;
    return;
}

void add_querry(trie &t, string s, int ind){
    int x = 0;
    for(char &c : s){
        int y = index(c);
        if(t.t[x][y] == -1)
            return;
        x = t.t[x][y];
    }
    query[x].push_back(ind);
    return;
}

void bejar(trie &t, int x){
    for(int &y : query[x])
        ki[y] = -ert[veg[y]];
    for(int y : t.inds[x])
        add(t2, vs[y]);
    for(int i = 0; i < 4; i++)
        if(t.t[x][i] != -1)
            bejar(t, t.t[x][i]);
    for(int &y : query[x])
        ki[y] += ert[veg[y]];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin>>n>>m;

    t1.init();
    t2.init();

    vs.resize(n);
    for(int i = 0; i < n; i++){
        cin>>vs[i];
        t1.add(vs[i], i);
        reverse(vs[i].begin(), vs[i].end());
    }
    query.resize(t1.t.size());

    ki.resize(m);
    veg.resize(m);
    for(int i = 0; i < m; i++){
        string a, b;
        cin>>a>>b;
        add_querry(t1, a, i);
        reverse(b.begin(), b.end());
        veg[i] = t2.add(b, i);
    }
    ert.resize(t2.t.size(), 0);

    bejar(t1, 0);
    for(int x : ki)
        cout<<x<<"\n";

    return 0;
}

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