oj.uz

Submission #1038839

# Submission time Handle Problem Language Result Execution time Memory
1038839 2024-07-30T08:14:02 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 746 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long double ld;
#define pb push_back
#define pf push_front
#define fi first
#define se second
const ll mod = 1e9+7, mxn = 1e5+7;
struct tri
{
    struct node
    {
        bitset<mxn> cnt; ll child[4];
        node() 
        {
            cnt = 0;
            for (ll i = 0; i < 4; i++) child[i] = 0;
        }
    };
    vector<node> trie = {node()};
    void add(string& x, ll id)
    {
        ll u = 0;
        for (ll i = 0; i < x.size(); i++)
        {
            if (!trie[u].child[x[i]-'A']) {trie.pb(node()); trie[u].child[x[i]-'A'] = trie.size()-1;}
            u = trie[u].child[x[i]-'A'];
        }
        trie[u].cnt[id] = 1;
    } 
    bitset<mxn> get(string& x)
    {
        ll u = 0;
        bitset<mxn> ans;
        for (ll i = 0; i < min((ll)1e5,(ll)x.size()); i++)
        {
            if (!trie[u].child[x[i]-'A']) return ans;
            u = trie[u].child[x[i]-'A'];
        }
        return trie[u].cnt;
    }
    void build(ll u) 
    {
        for (ll i = 0; i < 4; i++) if (trie[u].child[i]) 
        {
            build(trie[u].child[i]);
            trie[u].cnt ^= trie[trie[u].child[i]].cnt;
        }
    }
} tri1, tri2;
char trans(char x) 
{
    if (x == 'A') return 'A';
    if (x == 'U') return 'B';
    if (x == 'G') return 'C';
    return 'D';
}
ll n, m;
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // freopen("test.inp","r",stdin); freopen("test.out","w",stdout); freopen("test.err","w",stderr);
    cin >> n >> m;
    for (ll i = 1; i <= n; i++) 
    {
        string s; cin >> s;
        for (char& j : s) j = trans(j); 
        tri1.add(s,i);
        reverse(s.begin(),s.end());
        tri2.add(s,i);
    }
    tri1.build(0); tri2.build(0); 
    for (ll i = 1; i <= m; i++)
    {
        string a, b; cin >> a >> b;
        for (char& j : a) j = trans(j);
        for (char& j : b) j = trans(j);
        reverse(b.begin(),b.end());
        bitset<mxn> aa = tri1.get(a), bb = tri2.get(b);
        // cerr << aa[3] << ' ' << bb[3] << '\n';
        aa &= bb;
        cout << aa.count() << '\n';
    }
}

Compilation message

selling_rna.cpp: In member function 'void tri::add(std::string&, ll)':
selling_rna.cpp:25:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for (ll i = 0; i < x.size(); i++)
      |                        ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3632 KB Output is correct
2 Correct 3 ms 3688 KB Output is correct
3 Correct 4 ms 6684 KB Output is correct
4 Correct 3 ms 3144 KB Output is correct
5 Correct 5 ms 3608 KB Output is correct
6 Correct 3 ms 3012 KB Output is correct
7 Correct 3 ms 3580 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 746 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 828 KB Output is correct
2 Correct 196 ms 122740 KB Output is correct
3 Correct 275 ms 71412 KB Output is correct
4 Correct 157 ms 1104 KB Output is correct
5 Correct 192 ms 72364 KB Output is correct
6 Correct 236 ms 71812 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3632 KB Output is correct
2 Correct 3 ms 3688 KB Output is correct
3 Correct 4 ms 6684 KB Output is correct
4 Correct 3 ms 3144 KB Output is correct
5 Correct 5 ms 3608 KB Output is correct
6 Correct 3 ms 3012 KB Output is correct
7 Correct 3 ms 3580 KB Output is correct
8 Runtime error 746 ms 1048576 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -