oj.uz

Submission #44679

# Submission time Handle Problem Language Result Execution time Memory
44679 2018-04-04T19:36:55 Z choikiwon Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 64236 KB 
#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, ans;

    void init(vector<string> &V) {
        trie.push_back(vector<int>(6, -1));
        term.push_back(vector<int>());
        fail.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);
                }
                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 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]) ];

            int v = u;
            while(v) {
                for(int j = 0; j < term[v].size(); j++) {
                    ans[ term[v][j] ]++;
                }
                v = fail[v];
            }
        }
        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

selling_rna.cpp: In member function 'void aho_corasick::init(std::vector<std::__cxx11::basic_string<char> >&)':
selling_rna.cpp:24:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < V.size(); i++) {
                        ~~^~~~~~~~~~
selling_rna.cpp:26: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::query(std::__cxx11::string&)':
selling_rna.cpp:58:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < S.size(); i++) {
                        ~~^~~~~~~~~~
selling_rna.cpp:64:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int j = 0; j < term[v].size(); j++) {
                                ~~^~~~~~~~~~~~~~~~
selling_rna.cpp:70: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:89: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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 432 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 472 KB Output is correct
7 Correct 2 ms 640 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 22808 KB Output is correct
2 Correct 226 ms 22808 KB Output is correct
3 Execution timed out 1580 ms 64236 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 935 ms 64236 KB Output is correct
2 Correct 113 ms 64236 KB Output is correct
3 Correct 178 ms 64236 KB Output is correct
4 Correct 291 ms 64236 KB Output is correct
5 Correct 106 ms 64236 KB Output is correct
6 Correct 176 ms 64236 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 432 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 472 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 226 ms 22808 KB Output is correct
9 Correct 226 ms 22808 KB Output is correct
10 Execution timed out 1580 ms 64236 KB Time limit exceeded
11 Halted 0 ms 0 KB -