Submission #44685

#	Time	Username	Problem	Language	Result	Execution time	Memory
44685		choikiwon	Selling RNA Strands (JOI16_selling_rna)	C++17	0 / 100	205 ms	23524 KiB

selling_rna

#include<bits/stdc++.h>
using namespace std;

int f(char c) {
    if(c == 'A') return 0;
    if(c == 'G') return 1;
    if(c == 'C') return 2;
    if(c == 'U') return 3;
    if(c == '#') return 4;
    if(c == '@') return 5;
}

struct aho_corasick {
    vector<vector<int> > trie;
    vector<vector<int> > term;
    vector<int> fail, cnt, ans;

    void init(vector<string> &V) {
        trie.push_back(vector<int>(6, -1));
        term.push_back(vector<int>());
        fail.push_back(0);
        cnt.push_back(0);
        ans = vector<int>(V.size(), 0);

        for(int i = 0; i < V.size(); i++) {
            int u = 0;
            for(int j = 0; j < V[i].size(); j++) {
                if(trie[u][ f(V[i][j]) ] == -1) {
                    trie[u][ f(V[i][j]) ] = trie.size();
                    trie.push_back(vector<int>(6, -1));
                    term.push_back(vector<int>());
                    fail.push_back(0);
                    cnt.push_back(0);
                }
                u = trie[u][ f(V[i][j]) ];
            }
            term[u].push_back(i);
        }

        queue<int> q;
        for(int i = 0; i < 6; i++) {
            if(trie[0][i] != -1) q.push(trie[0][i]);
        }
        while(!q.empty()) {
            int u = q.front(); q.pop();

            for(int i = 0; i < 6; i++) {
                int v = trie[u][i];
                if(v != -1) {
                    int p = fail[u];
                    while(p && trie[p][i] == -1) p = fail[p];
                    fail[v] = trie[p][i] == -1? 0 : trie[p][i];
                    q.push(v);
                }
            }
        }
    }
    void dfs1(int u) {
        for(int i = 0; i < 6; i++) {
            int v = trie[u][i];
            if(v != -1) {
                dfs1(v);
            }
        }
        cnt[ fail[u] ] += cnt[u];
    }
    void dfs2(int u) {
        for(int i = 0; i < 6; i++) {
            int v = trie[u][i];
            if(v != -1) {
                dfs2(v);
            }
        }
        for(int i = 0; i < term[u].size(); i++) {
            ans[ term[u][i] ] += cnt[u];
        }
    }
    void query(string &S) {
        int u = 0;
        for(int i = 0; i < S.size(); i++) {
            while(u && trie[u][ f(S[i]) ] == -1) u = fail[u];
            if(trie[u][ f(S[i]) ] != -1) u = trie[u][ f(S[i]) ];
            cnt[u]++;
        }
        dfs1(0);
        dfs2(0);
        for(int i = 0; i < ans.size(); i++) {
            printf("%d\n", ans[i]);
        }
    }
} aho;

int N, M;
string S;
vector<string> V;

void getStr(string &s) {
    while(1) {
        char c = getchar();
        if(c == ' ' || c == '\n') break;
        s.push_back(c);
    }
}

int main() {
    scanf("%d %d", &N, &M);

    getchar();
    for(int i = 0; i < N; i++) {
        string s; getStr(s);
        S += s;
        S += '#';
        S += s;
        S += '@';
    }

    for(int i = 0; i < M; i++) {
        string p, q;
        getStr(p);
        getStr(q);
        V.push_back(q + '#' + p);
    }

    aho.init(V);
    aho.query(S);
}

Compilation message (stderr)

selling_rna.cpp: In member function 'void aho_corasick::init(std::vector<std::__cxx11::basic_string<char> >&)':
selling_rna.cpp:25:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < V.size(); i++) {
                        ~~^~~~~~~~~~
selling_rna.cpp:27:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < V[i].size(); j++) {
                            ~~^~~~~~~~~~~~~
selling_rna.cpp: In member function 'void aho_corasick::dfs2(int)':
selling_rna.cpp:74:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < term[u].size(); i++) {
                        ~~^~~~~~~~~~~~~~~~
selling_rna.cpp: In member function 'void aho_corasick::query(std::__cxx11::string&)':
selling_rna.cpp:80:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < S.size(); i++) {
                        ~~^~~~~~~~~~
selling_rna.cpp:87:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < ans.size(); i++) {
                        ~~^~~~~~~~~~~~
selling_rna.cpp: In function 'int f(char)':
selling_rna.cpp:11:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:106:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~~

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