Submission #1279960

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279960		nguyenphucanhkhoi	Selling RNA Strands (JOI16_selling_rna)	C++17	0 / 100	338 ms	305248 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;

#define TASK "DELSEQ"
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define fi first
#define se second
#define hash vector<int>
#define REP(i, n) for (int i = 1, _n = (n); i <= _n; i++)
#define REV(i, n) for (int i = (n); i >= 1; i--)
#define FOR(i, k, n) for (int i = (k), _n = (n); i <= _n; i++)
#define FOV(i, k, n) for (int i = (n), _n = (k); i >= _n; i--)
#define MASK(k) (1LL << (k))
#define BIT(i, n) (((n) >> ((i) - 1)) & 1)
#define OFF(i, n) ((n) & ~MASK((i) - 1))
#define ON(i, n) ((n) | MASK((i) - 1))
#define NUM_BIT(n) (__builtin_popcountll(n))

const int MAXN = 2000000 + 26;
int n, m, k;
string p, q, t, s[MAXN];

struct Node {
    Node *child[4];
    vector<int> pre;
    bool exist = false;

    Node() { FOR(i, 0, 3) child[i] = nullptr; }
};

struct Trie {
    Node *root;

    Trie() {
        root = new Node();
    }

    void add(string s, int r) {
        int t = s.length();
        Node* p = root;
        root->pre.push_back(r);
        REP(j, t) {
            int i = s[j - 1] - 'A';
            if (p->child[i] == nullptr) p->child[i] = new Node();
            p = p->child[i];
            p->pre.push_back(r);
        }
        p->exist = true;
    }
} t1, t2, t3;

string res;

void dfs(Node *p, bool first) {
    if (p->exist && first) s[++k] = res;
    if (!first) sort(p->pre.begin(), p->pre.end()); // sort để dùng lower_bound/upper_bound an toàn
    FOR(i, 0, 3) if (p->child[i] != nullptr) {
        char c = (char) ('A' + i);
        res += c;
        dfs(p->child[i], first);
        res.pop_back();
    }
}

string trans(string s) {
    string res = "";
    REP(i, s.length()) {
        if (s[i - 1] == 'A') res += 'A';
        if (s[i - 1] == 'G') res += 'B';
        if (s[i - 1] == 'C') res += 'C';
        if (s[i - 1] == 'U') res += 'D';
    }
    return res;
}

int find_first(Node *root) {
    // Sửa: trả giá trị nhỏ nhất từ vector pre của node (nếu có)
    if (!root->pre.empty()) return root->pre.front();
    // nếu không có pre, dò tiếp xuống con (mặc dù pre rỗng nghĩa là không có từ trong subtree)
    FOR(i, 0, 3) if (root->child[i] != nullptr) {
        int t = find_first(root->child[i]);
        if (t != -1) return t;
    }
    return -1;
}

int find_last(Node *root) {
    // Sửa: trả giá trị lớn nhất từ vector pre của node (nếu có)
    if (!root->pre.empty()) return root->pre.back();
    FOV(i, 0, 3) if (root->child[i] != nullptr) {
        int t = find_last(root->child[i]);
        if (t != -1) return t;
    }
    return -1;
}

int find_index(string pre, bool upper) {
    Node *p = t2.root;
    REP(j, pre.length()) {
        int i = pre[j - 1] - 'A';
        if (p->child[i] == nullptr) return -1;
        p = p->child[i];
    }
    if (upper) return find_last(p);
    return find_first(p);
}

Node *find_node(string str) {
    Node *p = t3.root;
    REP(j, str.length()) {
        int i = str[j - 1] - 'A';
        if (p->child[i] == nullptr) return nullptr;
        p = p->child[i];
    }
    return p;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    if (fopen(TASK ".INP", "r")) {
        freopen(TASK ".INP", "r", stdin);
        freopen(TASK ".OUT", "w", stdout);
    }
    cin >> n >> m;
    // đảm bảo k được khởi tạo trước khi dùng s[++k]
    k = 0; // <<-- SỬA: khởi tạo k
    REP(i, n) {
        cin >> t;
        t1.add(trans(t), -1);
    }
    dfs(t1.root, true);

    // thêm vào t2 và t3 giữ đúng indexing 1..k như code gốc
    REP(i, k) {
        t2.add(s[i], i);
        reverse(s[i].begin(), s[i].end());
        t3.add(s[i], i);
    }

    // SỬA: cần sort các pre của t2 và t3 trước khi dùng lower_bound/upper_bound
    dfs(t2.root, false);
    dfs(t3.root, false);

    while (m--) {
        cin >> p >> q;
        p = trans(p);
        q = trans(q);
        int l = find_index(p, false);
        int r = find_index(p, true);
        if (l == -1 || r == - 1) {
            cout << 0 << endl;
            continue;
        }
        reverse(q.begin(), q.end());
        Node *node = find_node(q);
        if (node == nullptr) {
            cout << 0 << endl;
            continue;
        }
        vector<int> &v = node->pre;
        int lp = lower_bound(v.begin(), v.end(), l) - v.begin();
        int rp = upper_bound(v.begin(), v.end(), r) - v.begin();
        int res = rp - lp;
        cout << res << endl;
    }
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         freopen(TASK ".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         freopen(TASK ".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40