oj.uz

Submission #44688

# Submission time Handle Problem Language Result Execution time Memory
44688 2018-04-04T20:11:33 Z choikiwon Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 362332 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;
}

vector<int> adj[5000010];
int cnt[5000010], ans[100010];

int cc[5000010];
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;
}

struct aho_corasick {
    vector<vector<int> > trie;
    vector<vector<int> > term;
    vector<int> fail;
    int n;

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

        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];
                    if(v) adj[ fail[v] ].push_back(v);
                    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]) ];
            cnt[u]++;
        }

        memset(cc, -1, sizeof(cc));
        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 < n; 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 function 'int dp(int)':
selling_rna.cpp:22:22: 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::init(std::vector<std::__cxx11::basic_string<char> >&)':
selling_rna.cpp:41:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < V.size(); i++) {
                        ~~^~~~~~~~~~
selling_rna.cpp:43: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:76:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < S.size(); i++) {
                        ~~^~~~~~~~~~
selling_rna.cpp:83:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < trie.size(); i++) {
                        ~~^~~~~~~~~~~~~
selling_rna.cpp:84:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < term[i].size(); j++) {
                            ~~^~~~~~~~~~~~~~~~
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:107: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 108 ms 137336 KB Output is correct
2 Correct 119 ms 137480 KB Output is correct
3 Correct 110 ms 137504 KB Output is correct
4 Correct 108 ms 137504 KB Output is correct
5 Correct 106 ms 137504 KB Output is correct
6 Correct 108 ms 137520 KB Output is correct
7 Correct 108 ms 137528 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 162292 KB Output is correct
2 Correct 274 ms 162292 KB Output is correct
3 Correct 658 ms 213568 KB Output is correct
4 Correct 638 ms 214300 KB Output is correct
5 Correct 1233 ms 270588 KB Output is correct
6 Correct 1243 ms 270588 KB Output is correct
7 Correct 962 ms 270588 KB Output is correct
8 Correct 1291 ms 317300 KB Output is correct
9 Execution timed out 1573 ms 362332 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 362332 KB Output is correct
2 Correct 129 ms 362332 KB Output is correct
3 Correct 129 ms 362332 KB Output is correct
4 Correct 132 ms 362332 KB Output is correct
5 Correct 125 ms 362332 KB Output is correct
6 Correct 132 ms 362332 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 137336 KB Output is correct
2 Correct 119 ms 137480 KB Output is correct
3 Correct 110 ms 137504 KB Output is correct
4 Correct 108 ms 137504 KB Output is correct
5 Correct 106 ms 137504 KB Output is correct
6 Correct 108 ms 137520 KB Output is correct
7 Correct 108 ms 137528 KB Output is correct
8 Correct 307 ms 162292 KB Output is correct
9 Correct 274 ms 162292 KB Output is correct
10 Correct 658 ms 213568 KB Output is correct
11 Correct 638 ms 214300 KB Output is correct
12 Correct 1233 ms 270588 KB Output is correct
13 Correct 1243 ms 270588 KB Output is correct
14 Correct 962 ms 270588 KB Output is correct
15 Correct 1291 ms 317300 KB Output is correct
16 Execution timed out 1573 ms 362332 KB Time limit exceeded
17 Halted 0 ms 0 KB -