oj.uz

답안 #691705

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
691705 2023-01-31T12:38:35 Z danikoynov Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1137 ms 1048576 KB 
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 1e5 + 10, alphabet = 26;

int n, m;
string rna[maxn];

struct query
{
    string p, q;
}ask[maxn];

void input()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        cin >> rna[i];
    for (int i = 1; i <= m; i ++)
        cin >> ask[i].p >> ask[i].q;
}

struct sub_trie
{
    unordered_map < int, sub_trie * > child;
    int cnt;

    sub_trie()
    {
        //for (int i = 0; i < alphabet; i ++)
          //  child[i] = NULL;
        cnt = 0;
    }

    int add(string &word, int pos)
    {
        cnt ++;
        if (pos == word.size())
            return 0;

        int go = word[pos] - 'A', to_add = 0;
        if (child[go] == NULL)
        {
            to_add = 0;
            child[go] = new sub_trie();
        }

        return to_add + child[go] -> add(word, pos + 1);
    }

    int find_suffix(string &word, int pos)
    {
        if (pos == word.size())
            return cnt;

        int go = word[pos] - 'A';
        if (child[go] == NULL)
            return 0;

        return child[go] -> find_suffix(word, pos + 1);
    }
};

void merge_sub_trie(sub_trie *&prim, sub_trie *sec)
{
    if (sec == NULL)
        return;

    if (prim == NULL)
    {
        prim = sec;
        return;
    }

    prim -> cnt += sec -> cnt;
    for (int i = 0; i < alphabet; i ++)
    {
        if (sec -> child[i] != NULL)
            merge_sub_trie(prim -> child[i],  sec -> child[i]);
    }
}

struct trie
{
    unordered_map < int, trie * > child;
    sub_trie *suffix;
    int suffix_len;
    vector < pair < string, int > > tasks;

    trie()
    {
        suffix_len = 0;
        suffix = new sub_trie();
    }

    void add(string &word, int pos)
    {
        if (pos == word.size())
        {
            string temp = word;
            reverse(temp.begin(), temp.end());
            suffix_len += suffix -> add(temp, 0);
            return;
        }

        int go = word[pos] - 'A';
        if (child[go] == NULL)
            child[go] = new trie();

        child[go] -> add(word, pos + 1);
    }

    void push_query(string &word, int pos, string &suff, int idx)
    {
        if (pos == word.size())
        {
            tasks.push_back({suff, idx});
            return;
        }

        int go = word[pos] - 'A';
        if (child[go] == NULL)
            return;

        child[go] -> push_query(word, pos + 1, suff, idx);
    }
};

trie *root = new trie();
void build_trie()
{
    for (int i = 1; i <= n; i ++)
    {
        root -> add(rna[i], 0);
    }
}

void insert_queries()
{
    for (int i = 1; i <= m; i ++)
    {
        reverse(ask[i].q.begin(), ask[i].q.end());
        root -> push_query(ask[i].p, 0, ask[i].q, i);
    }
}

int ans[maxn];
void dfs(trie *root)
{
    int mx = -1, max_len = -1;
    for (int i = 0; i < alphabet; i ++)
    {
        if (root -> child[i] != NULL)
        {
            dfs(root -> child[i]);
            if (root -> child[i] -> suffix_len > max_len)
            {
                max_len = root -> child[i] -> suffix_len;
                mx = i;
            }
        }
    }

    if (mx != - 1)
    {
        swap(root -> suffix, root -> child[mx] -> suffix);
    }

    for (int i = 0; i < alphabet; i ++)
    {
        if (root -> child[i] == NULL)
            continue;

        merge_sub_trie(root -> suffix, root -> child[i] -> suffix);
    }

    for (pair < string, int > cur : root -> tasks)
    {
        ans[cur.second] = root -> suffix -> find_suffix(cur.first, 0);
    }

}
void solve_queries()
{
    dfs(root);

    for (int i = 1; i <= m; i ++)
        cout << ans[i] << endl;
}

void solve()
{
    input();
    build_trie();
    insert_queries();
    solve_queries();
}

int main()
{
    speed();
    solve();
    return 0;
}
/**
*/

Compilation message

selling_rna.cpp: In member function 'int sub_trie::add(std::string&, int)':
selling_rna.cpp:48:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         if (pos == word.size())
      |             ~~~~^~~~~~~~~~~~~~
selling_rna.cpp: In member function 'int sub_trie::find_suffix(std::string&, int)':
selling_rna.cpp:63:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         if (pos == word.size())
      |             ~~~~^~~~~~~~~~~~~~
selling_rna.cpp: In member function 'void trie::add(std::string&, int)':
selling_rna.cpp:108:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         if (pos == word.size())
      |             ~~~~^~~~~~~~~~~~~~
selling_rna.cpp: In member function 'void trie::push_query(std::string&, int, std::string&, int)':
selling_rna.cpp:125:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |         if (pos == word.size())
      |             ~~~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 10196 KB Output is correct
2 Correct 6 ms 10104 KB Output is correct
3 Correct 6 ms 10196 KB Output is correct
4 Correct 6 ms 10100 KB Output is correct
5 Correct 5 ms 10188 KB Output is correct
6 Correct 6 ms 10016 KB Output is correct
7 Correct 7 ms 10100 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 645 ms 473364 KB Output is correct
2 Correct 650 ms 467208 KB Output is correct
3 Runtime error 1137 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 12428 KB Output is correct
2 Correct 30 ms 17168 KB Output is correct
3 Correct 31 ms 15768 KB Output is correct
4 Correct 24 ms 11596 KB Output is correct
5 Correct 49 ms 28288 KB Output is correct
6 Correct 38 ms 21308 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 10196 KB Output is correct
2 Correct 6 ms 10104 KB Output is correct
3 Correct 6 ms 10196 KB Output is correct
4 Correct 6 ms 10100 KB Output is correct
5 Correct 5 ms 10188 KB Output is correct
6 Correct 6 ms 10016 KB Output is correct
7 Correct 7 ms 10100 KB Output is correct
8 Correct 645 ms 473364 KB Output is correct
9 Correct 650 ms 467208 KB Output is correct
10 Runtime error 1137 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -