oj.uz

Submission #44692

# Submission time Handle Problem Language Result Execution time Memory
44692 2018-04-04T20:29:19 Z choikiwon Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 1469 ms 302084 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];

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;
}

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]++;
        }

        cc = vector<int>(trie.size(), -1);
        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 94 ms 117752 KB Output is correct
2 Correct 94 ms 117900 KB Output is correct
3 Correct 96 ms 117920 KB Output is correct
4 Correct 95 ms 117920 KB Output is correct
5 Correct 91 ms 117920 KB Output is correct
6 Correct 92 ms 117948 KB Output is correct
7 Correct 93 ms 118092 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 138524 KB Output is correct
2 Correct 257 ms 138524 KB Output is correct
3 Correct 617 ms 182500 KB Output is correct
4 Correct 602 ms 183188 KB Output is correct
5 Correct 1294 ms 226420 KB Output is correct
6 Correct 1199 ms 226420 KB Output is correct
7 Correct 954 ms 226420 KB Output is correct
8 Correct 1246 ms 264092 KB Output is correct
9 Correct 1469 ms 302084 KB Output is correct
10 Correct 216 ms 302084 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 302084 KB Output is correct
2 Correct 112 ms 302084 KB Output is correct
3 Correct 114 ms 302084 KB Output is correct
4 Correct 127 ms 302084 KB Output is correct
5 Correct 110 ms 302084 KB Output is correct
6 Correct 116 ms 302084 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 117752 KB Output is correct
2 Correct 94 ms 117900 KB Output is correct
3 Correct 96 ms 117920 KB Output is correct
4 Correct 95 ms 117920 KB Output is correct
5 Correct 91 ms 117920 KB Output is correct
6 Correct 92 ms 117948 KB Output is correct
7 Correct 93 ms 118092 KB Output is correct
8 Correct 284 ms 138524 KB Output is correct
9 Correct 257 ms 138524 KB Output is correct
10 Correct 617 ms 182500 KB Output is correct
11 Correct 602 ms 183188 KB Output is correct
12 Correct 1294 ms 226420 KB Output is correct
13 Correct 1199 ms 226420 KB Output is correct
14 Correct 954 ms 226420 KB Output is correct
15 Correct 1246 ms 264092 KB Output is correct
16 Correct 1469 ms 302084 KB Output is correct
17 Correct 216 ms 302084 KB Output is correct
18 Correct 113 ms 302084 KB Output is correct
19 Correct 112 ms 302084 KB Output is correct
20 Correct 114 ms 302084 KB Output is correct
21 Correct 127 ms 302084 KB Output is correct
22 Correct 110 ms 302084 KB Output is correct
23 Correct 116 ms 302084 KB Output is correct
24 Correct 252 ms 302084 KB Output is correct
25 Correct 260 ms 302084 KB Output is correct
26 Correct 254 ms 302084 KB Output is correct
27 Correct 294 ms 302084 KB Output is correct
28 Correct 263 ms 302084 KB Output is correct
29 Correct 196 ms 302084 KB Output is correct