# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
57149 | gs13105 | Selling RNA Strands (JOI16_selling_rna) | C++17 | 655 ms | 159108 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <iterator>
using namespace std;
int f(char x)
{
if(x == 'A')
return 0;
if(x == 'G')
return 1;
if(x == 'C')
return 2;
return 3;
}
struct ent1
{
int a[4];
vector<int> fin1, fin2;
};
struct ent2
{
int a[4];
int cnt;
};
vector<ent1> m1(1);
vector<ent2> m2(1);
string s[100010];
string p[100010];
string q[100010];
int pos[100010];
int res[100010];
void dfs(int c)
{
for(int &a : m1[c].fin2)
res[a] = -m2[pos[a]].cnt;
for(int &a : m1[c].fin1)
{
reverse(s[a].begin(), s[a].end());
int c2 = 0;
for(char &x : s[a])
{
int t = f(x);
if(!m2[c2].a[t])
break;
c2 = m2[c2].a[t];
m2[c2].cnt++;
}
}
for(int i = 0; i < 4; i++)
if(m1[c].a[i])
dfs(m1[c].a[i]);
for(int &a : m1[c].fin2)
res[a] += m2[pos[a]].cnt;
}
int main()
{
//freopen("in", "r", stdin);
//freopen("out", "w", stdout);
int n, m, i, j;
cin >> n >> m;
for(i = 0; i < n; i++)
cin >> s[i];
for(i = 0; i < m; i++)
cin >> p[i] >> q[i];
for(i = 0; i < n; i++)
{
int c = 0;
for(char &x : s[i])
{
int t = f(x);
if(!m1[c].a[t])
{
m1[c].a[t] = m1.size();
m1.resize(m1.size() + 1);
}
c = m1[c].a[t];
}
m1[c].fin1.push_back(i);
}
for(i = 0; i < m; i++)
{
int c = 0;
for(char &x : p[i])
{
int t = f(x);
if(!m1[c].a[t])
{
m1[c].a[t] = m1.size();
m1.resize(m1.size() + 1);
}
c = m1[c].a[t];
}
m1[c].fin2.push_back(i);
}
for(i = 0; i < m; i++)
{
reverse(q[i].begin(), q[i].end());
int c = 0;
for(char &x : q[i])
{
int t = f(x);
if(!m2[c].a[t])
{
m2[c].a[t] = m2.size();
m2.resize(m2.size() + 1);
}
c = m2[c].a[t];
}
pos[i] = c;
}
dfs(0);
for(i = 0; i < m; i++)
printf("%d\n", res[i]);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |