oj.uz

Submission #44687

# Submission time Handle Problem Language Result Execution time Memory
44687 2018-04-04T20:06:51 Z choikiwon Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 282208 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);
        adj.push_back(vector<int>());
        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:28:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < V.size(); i++) {
                        ~~^~~~~~~~~~
selling_rna.cpp:30: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:70: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:78:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < S.size(); i++) {
                        ~~^~~~~~~~~~
selling_rna.cpp:85:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < trie.size(); i++) {
                        ~~^~~~~~~~~~~~~
selling_rna.cpp:86:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < term[i].size(); j++) {
                            ~~^~~~~~~~~~~~~~~~
selling_rna.cpp:90: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:109: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 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 428 KB Output is correct
4 Correct 2 ms 428 KB Output is correct
5 Correct 3 ms 456 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 2 ms 464 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 30392 KB Output is correct
2 Correct 190 ms 30392 KB Output is correct
3 Correct 722 ms 92232 KB Output is correct
4 Correct 687 ms 93012 KB Output is correct
5 Correct 1395 ms 167816 KB Output is correct
6 Correct 1321 ms 167816 KB Output is correct
7 Correct 1114 ms 167816 KB Output is correct
8 Correct 1445 ms 227476 KB Output is correct
9 Execution timed out 1579 ms 282208 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 282208 KB Output is correct
2 Correct 18 ms 282208 KB Output is correct
3 Correct 22 ms 282208 KB Output is correct
4 Correct 20 ms 282208 KB Output is correct
5 Correct 19 ms 282208 KB Output is correct
6 Correct 22 ms 282208 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 428 KB Output is correct
4 Correct 2 ms 428 KB Output is correct
5 Correct 3 ms 456 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 2 ms 464 KB Output is correct
8 Correct 213 ms 30392 KB Output is correct
9 Correct 190 ms 30392 KB Output is correct
10 Correct 722 ms 92232 KB Output is correct
11 Correct 687 ms 93012 KB Output is correct
12 Correct 1395 ms 167816 KB Output is correct
13 Correct 1321 ms 167816 KB Output is correct
14 Correct 1114 ms 167816 KB Output is correct
15 Correct 1445 ms 227476 KB Output is correct
16 Execution timed out 1579 ms 282208 KB Time limit exceeded
17 Halted 0 ms 0 KB -