# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
68042 | 2018-08-15T19:41:48 Z | duality | Selling RNA Strands (JOI16_selling_rna) | C++11 | 6 ms | 1508 KB |
#include <bits/stdc++.h> using namespace std; #define mp make_pair #define pb push_back typedef pair<int,int> pii; typedef vector<int> vi; typedef vector<pii> vpii; #define SIZE 2000000 /* int index(char c) { if (c == 'A') return 0; else if (c == 'C') return 1; else if (c == 'G') return 2; else return 3; } int trie[SIZE+1][4],num = 0; int leaf[SIZE+1]; vector<pair<string,int> > queries[SIZE+1]; int ans[100000]; int trie2[SIZE+200000][4],sub[SIZE+200000],num2 = 0,p[SIZE+1]; int merge(int a,int b) { int i; for (i = 0; i < 4; i++) { if (trie2[a][i] != 0) { sub[b] += sub[trie2[a][i]]; if (trie2[b][i] == 0) trie2[b][i] = trie2[a][i]; else merge(trie2[a][i],trie2[b][i]); } } return 0; } vi path; int add(int a,int n) { int i; int c = a; for (i = path.size()-1; i >= 0; i--) { sub[c] += n; if (trie2[c][path[i]] == 0) trie2[c][path[i]] = ++num2; c = trie2[c][path[i]]; } sub[c] += n; return 0; } int doDFS(int u) { int i; int h = -1; for (i = 0; i < 4; i++) { if (trie[u][i] != 0) { path.pb(i); doDFS(trie[u][i]); if ((h == -1) || (sub[p[trie[u][i]]] > sub[h])) h = p[trie[u][i]]; path.pop_back(); } } if (h == -1) h = ++num2; if (leaf[u] > 0) add(h,leaf[u]); for (i = 0; i < 4; i++) { if ((trie[u][i] != 0) && (p[trie[u][i]] != h)) merge(p[trie[u][i]],h); } int j; p[u] = h; for (i = 0; i < queries[u].size(); i++) { int c = h; for (j = 0; j < queries[u][i].first.size(); j++) { int k = index(queries[u][i].first[j]); if (trie2[c][k] == 0) break; else c = trie2[c][k]; } if (j >= queries[u][i].first.size()) ans[queries[u][i].second] = sub[c]; } return 0; }*/ int main() { //cin.sync_with_stdio(0); //cout.sync_with_stdio(0); //cin.tie(0); int i,j; int N,M; string s1,s2; scanf("%d %d",&N,&M); string x[200]; char s[201]; for (i = 0; i < N; i++) { scanf("%s",s); x[i] = s; /*int c = 0; for (j = 0; j < s1.size(); j++) { if (trie[c][index(s1[j])] == 0) trie[c][index(s1[j])] = ++num; c = trie[c][index(s1[j])]; } leaf[c]++;*/ } for (i = 0; i < M; i++) { scanf("%s",s); s1 = s; scanf("%s",s); s2 = s; /*int c = 0; for (j = 0; j < s1.size(); j++) { if (trie[c][index(s1[j])] == 0) break; c = trie[c][index(s1[j])]; } if (j >= s1.size()) { reverse(s2.begin(),s2.end()); queries[c].pb(mp(s2,i)); }*/ int aaa = 0; for (j = 0; j < N; j++) { if (x[j].size() < min(s1.size(),s2.size())) continue; int k; for (k = 0; k < s1.size(); k++) { if (x[j][k] != s1[k]) break; } if (k >= s1.size()) { for (k = 0; k < s2.size(); k++) { if (x[j][x[j].size()-s2.size()+k] != s2[k]) break; } if (k >= s2.size()) aaa++; } //if ((x[j].substr(0,s1.size()) == s1) && (x[j].substr(x[j].size()-s2.size(),s2.size()) == s2)) aaa++; } printf("%d\n",aaa); } //doDFS(0); //for (i = 0; i < M; i++) cout << ans[i] << endl; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 3 ms | 488 KB | Output is correct |
3 | Correct | 3 ms | 488 KB | Output is correct |
4 | Correct | 3 ms | 628 KB | Output is correct |
5 | Correct | 3 ms | 628 KB | Output is correct |
6 | Correct | 2 ms | 628 KB | Output is correct |
7 | Correct | 2 ms | 628 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 6 ms | 1508 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 4 ms | 1508 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 3 ms | 488 KB | Output is correct |
3 | Correct | 3 ms | 488 KB | Output is correct |
4 | Correct | 3 ms | 628 KB | Output is correct |
5 | Correct | 3 ms | 628 KB | Output is correct |
6 | Correct | 2 ms | 628 KB | Output is correct |
7 | Correct | 2 ms | 628 KB | Output is correct |
8 | Runtime error | 6 ms | 1508 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
9 | Halted | 0 ms | 0 KB | - |