oj.uz

Submission #933058

# Submission time Handle Problem Language Result Execution time Memory
933058 2024-02-25T00:19:10 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
10 / 100
 1500 ms 972628 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);
    }   
}

struct Trie {
    struct Node {
        ptr(Node) child[26];
        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[*it - 'A'])
                node->child[*it - 'A'] = ptr(Node) (new Node);
            node->child[*it - 'A']->suf.push_back(i);
            node = node->child[*it - 'A'];
        }
    }

    vector<ll> get(string& s) {
        ptr(Node) node = root;
        for (auto it = s.begin(); it != s.end(); it++) {
            if (!node->child[*it - 'A'])
                return {};
            node = node->child[*it - 'A'];
        }
        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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 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 508 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 444 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 28500 KB Output is correct
2 Correct 195 ms 26960 KB Output is correct
3 Correct 932 ms 972628 KB Output is correct
4 Correct 846 ms 925012 KB Output is correct
5 Correct 533 ms 611556 KB Output is correct
6 Correct 543 ms 620680 KB Output is correct
7 Correct 351 ms 19028 KB Output is correct
8 Correct 362 ms 378192 KB Output is correct
9 Correct 331 ms 315984 KB Output is correct
10 Execution timed out 1539 ms 312016 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 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 508 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 444 KB Output is correct
8 Correct 79 ms 28500 KB Output is correct
9 Correct 195 ms 26960 KB Output is correct
10 Correct 932 ms 972628 KB Output is correct
11 Correct 846 ms 925012 KB Output is correct
12 Correct 533 ms 611556 KB Output is correct
13 Correct 543 ms 620680 KB Output is correct
14 Correct 351 ms 19028 KB Output is correct
15 Correct 362 ms 378192 KB Output is correct
16 Correct 331 ms 315984 KB Output is correct
17 Execution timed out 1539 ms 312016 KB Time limit exceeded
18 Halted 0 ms 0 KB -