Submission #668027

#	Time	Username	Problem	Language	Result	Execution time	Memory
668027		Ninja_Kunai	Selling RNA Strands (JOI16_selling_rna)	C++17	0 / 100	712 ms	1048576 KiB

selling_rna

/**
*    Author :  Nguyen Tuan Vu
*    Created : 02.12.2022
**/

#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define MASK(x) ((1)<<(x))
#define BIT(x, i) (((x)>>(i))&(1))
#define ALL(v)  (v).begin(), (v).end()
#define REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define FORD(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i)
#define db(val) "["#val" = "<<(val)<<"] "
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)

template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

using namespace std;

mt19937 jdg(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) {return l + jdg() % (r - l + 1);}

void file(){
    #define TASK "TASK"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
}

const int N = 1e5 + 5;
int n, nquery;
string s[N];

namespace sub2 {
	const int N = 5e3 + 5;

	struct TRIE {
		struct node {
			node *child[26];
			bitset <N> S;

			node() {
				REP(i, 26) child[i] = NULL;
			}
		} *root;

		TRIE() {
			root = new node();
		}

		void add(string &x, int ID) {
			node *p = root;
			for (auto c : x) {
				if (p -> child[c - 'A'] == NULL) p -> child[c - 'A'] = new node();
				p = p -> child[c - 'A'];
				p -> S[ID - 1] = 1;
			}
		}

		bitset <N> get(string &x) {
			node *p = root;
			for (auto c : x) {
				if (p -> child[c - 'A'] == NULL) return bitset <N> ();
				p = p -> child[c - 'A'];
			}

			return p -> S;
		}
	} trie[2];

	void solve() {
		FOR(i, 1, n) {
			trie[0].add(s[i], i);
			reverse(ALL(s[i]));
			trie[1].add(s[i], i);
		}

		while (nquery--) {
			string PREF, SUFF;
			cin >> PREF >> SUFF;

			bitset <N> between = (trie[0].get(PREF) & trie[1].get(SUFF));
			cout << between.count() << '\n';
		}
	}
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    file();

    cin >> n >> nquery;
    FOR(i, 1, n) cin >> s[i];
    if (n <= 5000) sub2::solve();
    cerr << "Time elapsed: " << TIME << " s.\n";
    return 0;
}

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

Compilation message (stderr)

selling_rna.cpp: In function 'void file()':
selling_rna.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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