Submission #933055

#	Time	Username	Problem	Language	Result	Execution time	Memory
933055		vjudge1	Selling RNA Strands (JOI16_selling_rna)	C++17	10 / 100	1553 ms	1048576 KiB

selling_rna

#include <bits/stdc++.h>

#define range(it, a, b) for (ll it = a; it < b; it++)
#define all(x) begin(x), end(x)
#define ll long long
#define ull unsigned long long
#define INF64 ((ll) 1 << 60)
#define INF32 (1 << 30)
#define mset multiset
#define uset unordered_set
#define umap unordered_map 
#define pqueue priority_queue
#define ptr(A) shared_ptr<A>

using namespace std;

void setio (string name) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (name.size()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }   
}

struct Trie {
    struct Node {
        ptr(Node) child[26];
        set<ll> pre, suf;
    };

    ptr(Node) root = ptr(Node) (new Node);

    void add(string& s, bool rev, ll i) {
        ptr(Node) node = root;
        if (rev) {
            for (auto it = s.rbegin(); it != s.rend(); it++) {
                if (!node->child[*it - 'A'])
                    node->child[*it - 'A'] = ptr(Node) (new Node);
                node->child[*it - 'A']->suf.insert(i);
                node = node->child[*it - 'A'];
            }
            return;
        }
        for (auto it = s.begin(); it != s.end(); it++) {
            if (!node->child[*it - 'A'])
                node->child[*it - 'A'] = ptr(Node) (new Node);
            node->child[*it - 'A']->pre.insert(i);
            node = node->child[*it - 'A'];
        }
    }

    set<ll> get(string& s, bool rev) {
        ptr(Node) node = root;
        if (rev) {
            for (auto it = s.rbegin(); it != s.rend(); it++) {
                if (!node->child[*it - 'A'])
                    return set<ll>();
                node = node->child[*it - 'A'];
            }
            return node->suf;
        }
        for (auto it = s.begin(); it != s.end(); it++) {
            if (!node->child[*it - 'A'])
                return set<ll>();
            node = node->child[*it - 'A'];
        }
        return node->pre;
    }
};

ll sunion (set<ll> a, set<ll> b) {
    ll cnt = 0;
    for (const ll& it : a) {
        if (b.count(it))
            cnt++;
    }
    return cnt;
}

ll n, m;
string s, t;

void solve() {
    cin >> n >> m;
    
    Trie tr;
    range(i, 0, n) {
        cin >> s;
        tr.add(s, 0, i);
        tr.add(s, 1, i);
    }

    while (m--) {
        cin >> s >> t;
        cout << sunion(tr.get(s, 0), tr.get(t, 1)) << '\n';
    }
}

int main () {
    setio("");
    ll t = 1; 
    // cin >> t;
    while (t--) solve();
}

Compilation message (stderr)

selling_rna.cpp: In function 'void setio(std::string)':
selling_rna.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen((name + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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