oj.uz

Submission #933061

# Submission time Handle Problem Language Result Execution time Memory
933061 2024-02-25T00:28:26 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 305744 KB 
#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);
    }   
}

ll cast (char c) {
    switch (c)
    {
    case 'A':
        return 0;
    case 'C':
        return 1;
    case 'G':
        return 2;
    case 'U':
        return 3;
    }
}

struct Trie {
    struct Node {
        ptr(Node) child[4];
        vector<ll> suf;
    };

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

    void add(string& s, ll i) {
        ptr(Node) node = root;
        for (auto it = s.begin(); it != s.end(); it++) {
            if (!node->child[cast(*it)])
                node->child[cast(*it)] = ptr(Node) (new Node);
            node->child[cast(*it)]->suf.push_back(i);
            node = node->child[cast(*it)];
        }
    }

    vector<ll> get(string& s) {
        ptr(Node) node = root;
        for (auto it = s.begin(); it != s.end(); it++) {
            if (!node->child[cast(*it)])
                return {};
            node = node->child[cast(*it)];
        }
        return node->suf;
    }
};

ll n, m;
vector<string> arr;
string s, t;

void solve() {
    cin >> n >> m;
    arr.resize(n);
    
    Trie tr;
    range(i, 0, n) {
        cin >> arr[i];
        tr.add(arr[i], i);
    }

    while (m--) {
        cin >> s >> t;
        vector<ll> ans = tr.get(s);
        ll cnt = 0;
        for (ll& it : ans) {
            if (arr[it].size() >= t.size() && t == arr[it].substr(arr[it].size() - t.size(), t.size()))
                cnt++;
        }
        cout << cnt << '\n';
    }
}

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

Compilation message

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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'long long int cast(char)':
selling_rna.cpp:38:1: warning: control reaches end of non-void function [-Wreturn-type]
   38 | }
      | ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 25500 KB Output is correct
2 Correct 182 ms 24924 KB Output is correct
3 Correct 452 ms 305744 KB Output is correct
4 Correct 385 ms 291348 KB Output is correct
5 Correct 236 ms 192592 KB Output is correct
6 Correct 240 ms 195316 KB Output is correct
7 Correct 335 ms 18264 KB Output is correct
8 Correct 186 ms 127056 KB Output is correct
9 Correct 174 ms 107632 KB Output is correct
10 Correct 1381 ms 107212 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1528 ms 3452 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 84 ms 25500 KB Output is correct
9 Correct 182 ms 24924 KB Output is correct
10 Correct 452 ms 305744 KB Output is correct
11 Correct 385 ms 291348 KB Output is correct
12 Correct 236 ms 192592 KB Output is correct
13 Correct 240 ms 195316 KB Output is correct
14 Correct 335 ms 18264 KB Output is correct
15 Correct 186 ms 127056 KB Output is correct
16 Correct 174 ms 107632 KB Output is correct
17 Correct 1381 ms 107212 KB Output is correct
18 Execution timed out 1528 ms 3452 KB Time limit exceeded
19 Halted 0 ms 0 KB -