oj.uz

Submission #57149

# Submission time Handle Problem Language Result Execution time Memory
57149 2018-07-14T07:11:27 Z gs13105 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 655 ms 159108 KB 
#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

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:86:18: warning: unused variable 'j' [-Wunused-variable]
     int n, m, i, j;
                  ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 9 ms 9836 KB Output is correct
3 Correct 9 ms 9876 KB Output is correct
4 Correct 9 ms 9876 KB Output is correct
5 Correct 9 ms 9876 KB Output is correct
6 Correct 9 ms 9876 KB Output is correct
7 Correct 11 ms 9876 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 18072 KB Output is correct
2 Correct 219 ms 22172 KB Output is correct
3 Correct 628 ms 155972 KB Output is correct
4 Correct 586 ms 155992 KB Output is correct
5 Correct 496 ms 155992 KB Output is correct
6 Correct 570 ms 155992 KB Output is correct
7 Correct 347 ms 155992 KB Output is correct
8 Correct 655 ms 155992 KB Output is correct
9 Correct 540 ms 155992 KB Output is correct
10 Correct 377 ms 155992 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 155992 KB Output is correct
2 Correct 76 ms 155992 KB Output is correct
3 Correct 63 ms 155992 KB Output is correct
4 Correct 57 ms 155992 KB Output is correct
5 Correct 64 ms 155992 KB Output is correct
6 Correct 72 ms 155992 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 9 ms 9836 KB Output is correct
3 Correct 9 ms 9876 KB Output is correct
4 Correct 9 ms 9876 KB Output is correct
5 Correct 9 ms 9876 KB Output is correct
6 Correct 9 ms 9876 KB Output is correct
7 Correct 11 ms 9876 KB Output is correct
8 Correct 175 ms 18072 KB Output is correct
9 Correct 219 ms 22172 KB Output is correct
10 Correct 628 ms 155972 KB Output is correct
11 Correct 586 ms 155992 KB Output is correct
12 Correct 496 ms 155992 KB Output is correct
13 Correct 570 ms 155992 KB Output is correct
14 Correct 347 ms 155992 KB Output is correct
15 Correct 655 ms 155992 KB Output is correct
16 Correct 540 ms 155992 KB Output is correct
17 Correct 377 ms 155992 KB Output is correct
18 Correct 70 ms 155992 KB Output is correct
19 Correct 76 ms 155992 KB Output is correct
20 Correct 63 ms 155992 KB Output is correct
21 Correct 57 ms 155992 KB Output is correct
22 Correct 64 ms 155992 KB Output is correct
23 Correct 72 ms 155992 KB Output is correct
24 Correct 273 ms 155992 KB Output is correct
25 Correct 272 ms 155992 KB Output is correct
26 Correct 265 ms 155992 KB Output is correct
27 Correct 613 ms 159108 KB Output is correct
28 Correct 351 ms 159108 KB Output is correct
29 Correct 236 ms 159108 KB Output is correct