Submission #671099

#	Time	Username	Problem	Language	Result	Execution time	Memory
671099		GusterGoose27	Selling RNA Strands (JOI16_selling_rna)	C++11	100 / 100	577 ms	671136 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5;
int ans[MAXN];
vector<int> queries[MAXN];
int n, m;
map<char, int> conv({{'A', 0}, {'U', 1}, {'G', 2}, {'C', 3}});

class Trie {
public:
	Trie *nxt[4];
	int sz;
	Trie *rev_t;
	int term = 0; // num ending at this position
	vector<int> rev_queries;
	vector<int> seq;
	Trie() {
		sz = 0;
		for (int i = 0; i < 4; i++) nxt[i] = nullptr;
	}
	void merge(Trie *oth) {
		sz += oth->sz;
		for (int i = 0; i < 4; i++) {
			if (nxt[i] == nullptr) nxt[i] = oth->nxt[i];
			else if (oth->nxt[i] != nullptr) nxt[i]->merge(oth->nxt[i]);
		}
		// delete oth;
	}
	void ins(vector<int> &s, int p = 0, int num = 1) {
		sz += num;
		if (p == s.size()) {
			term += num;
			seq = s;
			return;
		}
		if (nxt[s[p]] == nullptr) nxt[s[p]] = new Trie();
		nxt[s[p]]->ins(s, p+1, num);
	}
	void ins_query(vector<int> &f, int p, int id) {
		if (p == f.size()) rev_queries.push_back(id);
		else {
			if (nxt[f[p]] != nullptr) nxt[f[p]]->ins_query(f, p+1, id);
		}
	}
	void dfs() {
		for (int i = 0; i < 4; i++) if (nxt[i] != nullptr) nxt[i]->dfs();
		rev_t = new Trie();
		if (term) {
			reverse(seq.begin(), seq.end());
			rev_t->ins(seq, 0, term);
		}
		for (int i = 0; i < 4; i++) if (nxt[i] != nullptr) rev_t->merge(nxt[i]->rev_t);
		for (int v: rev_queries) {
			reverse(queries[v].begin(), queries[v].end());
			ans[v] = rev_t->count(queries[v]);
		}
	}
	int count(vector<int> &v, int p = 0) {
		if (p == v.size()) return sz;
		if (nxt[v[p]] == nullptr) return 0;
		return nxt[v[p]]->count(v, p+1);
	}
};

Trie *tree;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m;
	tree = new Trie();
	for (int i = 0; i < n; i++) {
		string s; cin >> s;
		vector<int> v;
		for (int j = 0; j < s.size(); j++) v.push_back(conv[s[j]]);
		tree->ins(v);
	}
	for (int i = 0; i < m; i++) {
		string s1, s2; cin >> s1 >> s2;
		vector<int> v1;
		for (int j = 0; j < s1.size(); j++) v1.push_back(conv[s1[j]]);
		for (int j = 0; j < s2.size(); j++) queries[i].push_back(conv[s2[j]]);
		tree->ins_query(v1, 0, i);
	}
	tree->dfs();
	for (int i = 0; i < m; i++) cout << ans[i] << "\n";
}

Compilation message (stderr)

selling_rna.cpp: In member function 'void Trie::ins(std::vector<int>&, int, int)':
selling_rna.cpp:33:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   if (p == s.size()) {
      |       ~~^~~~~~~~~~~
selling_rna.cpp: In member function 'void Trie::ins_query(std::vector<int>&, int, int)':
selling_rna.cpp:42:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   if (p == f.size()) rev_queries.push_back(id);
      |       ~~^~~~~~~~~~~
selling_rna.cpp: In member function 'int Trie::count(std::vector<int>&, int)':
selling_rna.cpp:61:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   if (p == v.size()) return sz;
      |       ~~^~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:76:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   for (int j = 0; j < s.size(); j++) v.push_back(conv[s[j]]);
      |                   ~~^~~~~~~~~~
selling_rna.cpp:82:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   for (int j = 0; j < s1.size(); j++) v1.push_back(conv[s1[j]]);
      |                   ~~^~~~~~~~~~~
selling_rna.cpp:83:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |   for (int j = 0; j < s2.size(); j++) queries[i].push_back(conv[s2[j]]);
      |                   ~~^~~~~~~~~~~

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