답안 #44687 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
44687	2018-04-04T20:06:51 Z	choikiwon	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	1500 ms	282208 KB

selling_rna

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #44687

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 0 / 25.0

Subtask #3 25.0 / 25.0

Subtask #4 0 / 40.0

Subtask #1
10.0 / 10.0

Subtask #2
0 / 25.0

Subtask #3
25.0 / 25.0

Subtask #4
0 / 40.0