oj.uz

Submission #1034692

# Submission time Handle Problem Language Result Execution time Memory
1034692 2024-07-25T16:48:06 Z baotoan655 Selling RNA Strands (JOI16_selling_rna) C++17
10 / 100
 1500 ms 377668 KB 
#include <bits/stdc++.h>
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define REV(i, b, a) for(int i = (b); i >= (a); --i)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define ll long long
#define fi first 
#define se second

using namespace std;

set<int> empty_set;
int n, q;
int num[26];

struct trie {
    struct node {
        node* con[4];
        set<int> se;
        node() {
            for(int i = 0; i < 4; ++i) con[i] = NULL;
            se.clear();
        };
    };
    node* root;
    trie() {
        root = new node();
    };

    void add_string(const string &s, int id) {
        node* pos = root;
        for(char ch : s) {
            int c = num[ch - 'A'];
            if(pos->con[c] == NULL) pos->con[c] = new node();
            pos = pos->con[c];
            pos->se.insert(id);
        }
    };
    set<int> get(const string &s) {
        node* pos = root;
        for(char ch : s) {
            int c = num[ch - 'A'];
            if(pos->con[c] == NULL) return empty_set;
            pos = pos->con[c];
        }
        return pos->se;
    }
} tr1, tr2;

void solve(int tc) {
    num['A' - 'A'] = 0;
    num['U' - 'A'] = 1;
    num['G' - 'A'] = 2;
    num['C' - 'A'] = 3;
    cin >> n >> q;
    string str;
    FOR(i, 1, n) {
        cin >> str;
        tr1.add_string(str, i);
        reverse(str.begin(), str.end());
        tr2.add_string(str, i);
    }
    while(q--) {
        string s1, s2;
        cin >> s1 >> s2;
        reverse(s2.begin(), s2.end());
        set<int> se1 = tr1.get(s1);
        set<int> se2 = tr2.get(s2);

        int ans = 0;
        for(int x : se1) {
            if(se2.find(x) != se2.end()) ++ans;
        }
        cout << ans << '\n';
    }
    return;
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    file("A");
    int tc = 1; 
    // cin >> tc;
    for(int i = 1; i <= tc; ++i) solve(tc);
    return (0);
}

Compilation message

selling_rna.cpp: In function 'int32_t main()':
selling_rna.cpp:2:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:82:5: note: in expansion of macro 'file'
   82 |     file("A");
      |     ^~~~
selling_rna.cpp:2:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:82:5: note: in expansion of macro 'file'
   82 |     file("A");
      |     ^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 716 ms 377668 KB Output is correct
2 Execution timed out 1585 ms 367356 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1557 ms 12372 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 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 456 KB Output is correct
8 Correct 716 ms 377668 KB Output is correct
9 Execution timed out 1585 ms 367356 KB Time limit exceeded
10 Halted 0 ms 0 KB -