oj.uz

Submission #44686

# Submission time Handle Problem Language Result Execution time Memory
44686 2018-04-04T20:04:55 Z choikiwon Selling RNA Strands (JOI16_selling_rna) C++17
0 / 100
 1500 ms 168076 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;
    vector<vector<int> > adj;
    vector<int> 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);
                    adj.push_back(vector<int>());
                    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];
                    if(v) adj[ fail[v] ].push_back(v);
                    q.push(v);
                }
            }
        }
    }

    vector<int> cc;
    int dp(int u) {
        int &ret = cc[u];
        if(ret != -1) return ret;

        ret = cnt[u];
        for(int i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i];
            ret += dp(v);
        }
        return ret;
    }
    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]++;
        }

        cc = vector<int>(trie.size(), -1);
        for(int i = 0; i < trie.size(); i++) {
            for(int j = 0; j < term[i].size(); j++) {
                ans[ term[i][j] ] += dp(i);
            }
        }
        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:27:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < V.size(); i++) {
                        ~~^~~~~~~~~~
selling_rna.cpp:29: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 'int aho_corasick::dp(int)':
selling_rna.cpp:69:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < adj[u].size(); i++) {
                        ~~^~~~~~~~~~~~~~~
selling_rna.cpp: In member function 'void aho_corasick::query(std::__cxx11::string&)':
selling_rna.cpp:77:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < S.size(); i++) {
                        ~~^~~~~~~~~~
selling_rna.cpp:84:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < trie.size(); i++) {
                        ~~^~~~~~~~~~~~~
selling_rna.cpp:85:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < term[i].size(); j++) {
                            ~~^~~~~~~~~~~~~~~~
selling_rna.cpp:89: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:108: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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 2 ms 500 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Runtime error 3 ms 756 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 30752 KB Output is correct
2 Correct 173 ms 30752 KB Output is correct
3 Correct 679 ms 92600 KB Output is correct
4 Correct 669 ms 93304 KB Output is correct
5 Execution timed out 1573 ms 168076 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 168076 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 2 ms 500 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Runtime error 3 ms 756 KB Execution killed with signal 11 (could be triggered by violating memory limits)