oj.uz

Submission #44689

# Submission time Handle Problem Language Result Execution time Memory
44689 2018-04-04T20:16:58 Z choikiwon Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 1445 ms 313804 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], pnt[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<int> fail;
    int n;

    void init(vector<string> &V) {
        trie.push_back(vector<int>(6, -1));
        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));
                    fail.push_back(0);
                }
                u = trie[u][ f(V[i][j]) ];
            }
            pnt[i] = u;
        }

        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 < n; i++) {
            printf("%d\n", dp(pnt[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:39:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < V.size(); i++) {
                        ~~^~~~~~~~~~
selling_rna.cpp:41: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:73:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < S.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:99: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 118 ms 137336 KB Output is correct
2 Correct 111 ms 137356 KB Output is correct
3 Correct 107 ms 137380 KB Output is correct
4 Correct 113 ms 137528 KB Output is correct
5 Correct 113 ms 137528 KB Output is correct
6 Correct 129 ms 137528 KB Output is correct
7 Correct 161 ms 137528 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 157456 KB Output is correct
2 Correct 322 ms 157456 KB Output is correct
3 Correct 698 ms 200080 KB Output is correct
4 Correct 636 ms 200564 KB Output is correct
5 Correct 1243 ms 241380 KB Output is correct
6 Correct 1165 ms 241380 KB Output is correct
7 Correct 933 ms 241380 KB Output is correct
8 Correct 1242 ms 277052 KB Output is correct
9 Correct 1445 ms 313804 KB Output is correct
10 Correct 225 ms 313804 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 313804 KB Output is correct
2 Correct 121 ms 313804 KB Output is correct
3 Correct 130 ms 313804 KB Output is correct
4 Correct 128 ms 313804 KB Output is correct
5 Correct 126 ms 313804 KB Output is correct
6 Correct 127 ms 313804 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 137336 KB Output is correct
2 Correct 111 ms 137356 KB Output is correct
3 Correct 107 ms 137380 KB Output is correct
4 Correct 113 ms 137528 KB Output is correct
5 Correct 113 ms 137528 KB Output is correct
6 Correct 129 ms 137528 KB Output is correct
7 Correct 161 ms 137528 KB Output is correct
8 Correct 384 ms 157456 KB Output is correct
9 Correct 322 ms 157456 KB Output is correct
10 Correct 698 ms 200080 KB Output is correct
11 Correct 636 ms 200564 KB Output is correct
12 Correct 1243 ms 241380 KB Output is correct
13 Correct 1165 ms 241380 KB Output is correct
14 Correct 933 ms 241380 KB Output is correct
15 Correct 1242 ms 277052 KB Output is correct
16 Correct 1445 ms 313804 KB Output is correct
17 Correct 225 ms 313804 KB Output is correct
18 Correct 128 ms 313804 KB Output is correct
19 Correct 121 ms 313804 KB Output is correct
20 Correct 130 ms 313804 KB Output is correct
21 Correct 128 ms 313804 KB Output is correct
22 Correct 126 ms 313804 KB Output is correct
23 Correct 127 ms 313804 KB Output is correct
24 Correct 258 ms 313804 KB Output is correct
25 Correct 271 ms 313804 KB Output is correct
26 Correct 254 ms 313804 KB Output is correct
27 Correct 299 ms 313804 KB Output is correct
28 Correct 273 ms 313804 KB Output is correct
29 Correct 213 ms 313804 KB Output is correct