oj.uz

Submission #44677

# Submission time Handle Problem Language Result Execution time Memory
44677 2018-04-04T19:34:08 Z choikiwon Selling RNA Strands (JOI16_selling_rna) C++17
60 / 100
 1500 ms 216252 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];
                    //term[v] += term[ fail[v] ];

                    for(int j = 0; j < term[ fail[v] ].size(); j++) {
                        term[v].push_back(term[ fail[v] ][j]);
                    }

                    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]) ];

            for(int j = 0; j < term[u].size(); j++) {
                ans[ term[u][j] ]++;
            }
        }
        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:53:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for(int j = 0; j < term[ fail[v] ].size(); j++) {
                                    ~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In member function 'void aho_corasick::query(std::__cxx11::string&)':
selling_rna.cpp:64:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < S.size(); i++) {
                        ~~^~~~~~~~~~
selling_rna.cpp:68:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < term[u].size(); j++) {
                            ~~^~~~~~~~~~~~~~~~
selling_rna.cpp:72: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:91: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 376 KB Output is correct
3 Correct 3 ms 428 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 672 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 23220 KB Output is correct
2 Correct 221 ms 23220 KB Output is correct
3 Correct 459 ms 72116 KB Output is correct
4 Correct 455 ms 76128 KB Output is correct
5 Correct 798 ms 130484 KB Output is correct
6 Correct 789 ms 132980 KB Output is correct
7 Correct 823 ms 140388 KB Output is correct
8 Correct 1087 ms 182572 KB Output is correct
9 Correct 1158 ms 216252 KB Output is correct
10 Correct 201 ms 216252 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 903 ms 216252 KB Output is correct
2 Correct 85 ms 216252 KB Output is correct
3 Correct 156 ms 216252 KB Output is correct
4 Correct 261 ms 216252 KB Output is correct
5 Correct 88 ms 216252 KB Output is correct
6 Correct 147 ms 216252 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 376 KB Output is correct
3 Correct 3 ms 428 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 672 KB Output is correct
8 Correct 199 ms 23220 KB Output is correct
9 Correct 221 ms 23220 KB Output is correct
10 Correct 459 ms 72116 KB Output is correct
11 Correct 455 ms 76128 KB Output is correct
12 Correct 798 ms 130484 KB Output is correct
13 Correct 789 ms 132980 KB Output is correct
14 Correct 823 ms 140388 KB Output is correct
15 Correct 1087 ms 182572 KB Output is correct
16 Correct 1158 ms 216252 KB Output is correct
17 Correct 201 ms 216252 KB Output is correct
18 Correct 903 ms 216252 KB Output is correct
19 Correct 85 ms 216252 KB Output is correct
20 Correct 156 ms 216252 KB Output is correct
21 Correct 261 ms 216252 KB Output is correct
22 Correct 88 ms 216252 KB Output is correct
23 Correct 147 ms 216252 KB Output is correct
24 Correct 209 ms 216252 KB Output is correct
25 Correct 293 ms 216252 KB Output is correct
26 Correct 227 ms 216252 KB Output is correct
27 Correct 273 ms 216252 KB Output is correct
28 Execution timed out 1590 ms 216252 KB Time limit exceeded
29 Halted 0 ms 0 KB -