oj.uz

Submission #1048162

# Submission time Handle Problem Language Result Execution time Memory
1048162 2024-08-08T03:27:46 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 148 ms 264800 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second

const int ar = 1e5 + 5;
const int N = 2e6;
int n, m;
string s[ar], r[ar];
string p[ar], q[ar];
const int NUMBEROFNODES = 4 * 2000000 + 5;
void remake(string &s)
{
    for (auto &u : s)
    {
        if (u == 'C') u = 'a';
        else if (u == 'U') u = 'b';
        else if (u == 'G') u = 'c';
        else u = 'd';
    }
}
int make[N + 5];
struct Trie{
    int timedfs = 0;
    struct Node{
        int child[5];
        int exist, cnt;
        int id;
        int in, out;
    } nodes[NUMBEROFNODES];

    int cur;
    Trie() : cur(0) {
        memset(nodes[0].child, -1, sizeof(nodes[cur].child));
        nodes[0].exist = nodes[0].cnt = 0;
    };

    int new_node() {
        cur++;
        memset(nodes[cur].child, -1, sizeof(nodes[cur].child));
        nodes[cur].exist = nodes[cur].cnt = 0;
        return cur;
    }

    void add_string(string &s, int p, bool t) {
        int pos = 0;
        for (auto f : s) {
            int c = f - 'a';
            if (nodes[pos].child[c] == -1){
                nodes[pos].child[c] = new_node();
            }
            pos = nodes[pos].child[c];
            nodes[pos].cnt++;

        }
        nodes[pos].exist++;
        nodes[pos].id =  p;
        if (t) make[p] = pos;
    }

    pair<int, int> find(string &s) {
        int pos = 0;
        for (auto f : s) {
            int c = f - 'a';
            if (nodes[pos].child[c] == -1) return {-1, -1};
            pos = nodes[pos].child[c];
        }
        return {nodes[pos].in, nodes[pos].out}; // Kiểm tra có xâu nào
                                        // kết thúc tại đỉnh này hay không
    }
    void dfs(int u)
    {
        nodes[u].in = ++timedfs;
        for (int i = 0; i <= 4; i++)
        {
            if (nodes[u].child[i] == -1) continue;
            //ok = true;
            dfs(nodes[u].child[i]);
        }
        nodes[u].out = timedfs;
    }
} pre, suf;
vector<pair<int, int>> point[N + 5];
void make_point(int u)
{
    bool ok = false;
    for (int i = 0; i <= 4; i++)
    {
        if (suf.nodes[u].child[i] == -1) continue;
        ok = true;
        make_point(suf.nodes[u].child[i]);
    }
    int id = suf.nodes[u].id;
    id = make[id];
    if (suf.nodes[u].exist) point[pre.nodes[id].in].push_back({suf.nodes[u].in, pre.nodes[id].exist});
}
int ans[ar];
struct BIT
{
    int bit[N + 5];
    void update(int u, int v)
    {
        while(u <= N)
        {
            bit[u] += v;
            u += u & (-u);
        }
    }
    int get(int u)
    {
        int ans = 0;
        while(u > 0)
        {
            ans += bit[u];
            u -= u & (-u);
        }
        return ans;
    }
} tree;
vector<tuple<int, int, int>> sta[N + 5], en[N + 5];
void get()
{
    for (int x = 1; x <= N; x++)
    {
        for (auto [y, v] : point[x]) tree.update(y, v);
        for (auto [l, r, i] : sta[x])
        {
            ans[i] -= tree.get(r) - tree.get(l - 1);
        }
        for (auto [l, r, i] : en[x])
        {
            ans[i] += tree.get(r) - tree.get(l - 1);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
        r[i] = s[i];
        reverse(r[i].begin(), r[i].end());
        remake(s[i]);
        remake(r[i]);
        //cout << s[i] << ' ' << r[i] << '\n';
        pre.add_string(s[i], i, 1);
        suf.add_string(r[i], i, 0);
    }
    pre.dfs(0);
    suf.dfs(0);
    make_point(0);
    for (int i = 1; i <= m; i++)
    {
        cin >> p[i] >> q[i];
        remake(p[i]);
        remake(q[i]);
        reverse(q[i].begin(), q[i].end());
        auto [l1, r1] = pre.find(p[i]);
        auto [l2, r2] = suf.find(q[i]);
        if (l1 == -1) continue;
        //cout << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << '\n';
        sta[l1 - 1].push_back({l2, r2, i});
        en[r1].push_back({l2, r2, i});
    }
    get();
    for (int i = 1; i <= m; i++) cout << ans[i] << '\n';
}

Compilation message

selling_rna.cpp: In function 'void make_point(int)':
selling_rna.cpp:87:10: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   87 |     bool ok = false;
      |          ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 163932 KB Output is correct
2 Correct 32 ms 161884 KB Output is correct
3 Correct 27 ms 163932 KB Output is correct
4 Correct 26 ms 164064 KB Output is correct
5 Correct 28 ms 161880 KB Output is correct
6 Correct 26 ms 161884 KB Output is correct
7 Correct 25 ms 161992 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 249468 KB Output is correct
2 Correct 111 ms 246264 KB Output is correct
3 Correct 102 ms 242512 KB Output is correct
4 Correct 97 ms 238928 KB Output is correct
5 Correct 146 ms 263188 KB Output is correct
6 Correct 148 ms 264800 KB Output is correct
7 Correct 56 ms 169556 KB Output is correct
8 Correct 107 ms 226152 KB Output is correct
9 Correct 98 ms 216660 KB Output is correct
10 Correct 78 ms 212364 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 163792 KB Output is correct
2 Correct 35 ms 165468 KB Output is correct
3 Correct 38 ms 163724 KB Output is correct
4 Correct 39 ms 163148 KB Output is correct
5 Correct 33 ms 165208 KB Output is correct
6 Correct 35 ms 163412 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 163932 KB Output is correct
2 Correct 32 ms 161884 KB Output is correct
3 Correct 27 ms 163932 KB Output is correct
4 Correct 26 ms 164064 KB Output is correct
5 Correct 28 ms 161880 KB Output is correct
6 Correct 26 ms 161884 KB Output is correct
7 Correct 25 ms 161992 KB Output is correct
8 Correct 117 ms 249468 KB Output is correct
9 Correct 111 ms 246264 KB Output is correct
10 Correct 102 ms 242512 KB Output is correct
11 Correct 97 ms 238928 KB Output is correct
12 Correct 146 ms 263188 KB Output is correct
13 Correct 148 ms 264800 KB Output is correct
14 Correct 56 ms 169556 KB Output is correct
15 Correct 107 ms 226152 KB Output is correct
16 Correct 98 ms 216660 KB Output is correct
17 Correct 78 ms 212364 KB Output is correct
18 Correct 35 ms 163792 KB Output is correct
19 Correct 35 ms 165468 KB Output is correct
20 Correct 38 ms 163724 KB Output is correct
21 Correct 39 ms 163148 KB Output is correct
22 Correct 33 ms 165208 KB Output is correct
23 Correct 35 ms 163412 KB Output is correct
24 Correct 104 ms 236772 KB Output is correct
25 Correct 121 ms 238160 KB Output is correct
26 Correct 104 ms 235604 KB Output is correct
27 Correct 93 ms 229332 KB Output is correct
28 Correct 87 ms 181076 KB Output is correct
29 Correct 55 ms 167508 KB Output is correct