Submission #44689

#TimeUsernameProblemLanguageResultExecution timeMemory
44689choikiwonSelling RNA Strands (JOI16_selling_rna)C++17
100 / 100
1445 ms313804 KiB
#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 (stderr)

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);
     ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...