Submission #344377

#	Time	Username	Problem	Language	Result	Execution time	Memory
344377		aZvezda	Selling RNA Strands (JOI16_selling_rna)	C++14	0 / 100	1609 ms	834044 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define out(x) "{" << (#x) << ": " << x << "} "

const int MAX_N = 1e6 + 10;
struct Node {
	int mp[4];
	int cnt;
	Node() {
		for(int i = 0; i < 4; i ++) {
			mp[i] = -1;
		}
		cnt = 0;
	}
};

struct Trie {
	vector<Node> nds;
	Trie() {
		nds.resize(1);
	}
	void add(const string &str) {
		int curr = 0;
		nds[curr].cnt ++;
		for(int i = 0; i < str.size(); i ++) {
			if(nds[curr].mp[str[i]] == -1) {
				nds[curr].mp[str[i]] = nds.size();
				nds.push_back(Node());
			}
			curr = nds[curr].mp[str[i]];
			nds[curr].cnt ++;
		}
	}
	int size() {return nds.size();}
	int cnt(const string &str) {
		int curr = 0;
		for(int i = 0; i < str.size(); i ++) {
			curr = nds[i].mp[str[i]];
			if(curr == -1) {return 0;}
		}
		return nds[curr].cnt;
	}
	void outputtrie(int x, vector<int> out) {
		cout << x << " " << nds[x].cnt << " ";
		for(auto it : out) {
			cout << it;
		}
		cout << endl;
		for(int i = 0; i < 4; i ++) {
			if(nds[x].mp[i] == -1) {continue;}
			out.push_back(i);
			outputtrie(nds[x].mp[i], out);
			out.pop_back();
		} 
	}
};

vector<int> fin[MAX_N], quer[MAX_N];
int mp[MAX_N][4];
int n, q, ans[MAX_N], cnt = 1;
string text[MAX_N];
string in[MAX_N][2];

void buildTrie() {
	for(int i = 0; i < n; i ++) {
		int curr = 0;
		for(int j = 0; j < text[i].size(); j ++) {
			if(mp[curr][text[i][j]] == -1) {
				mp[curr][text[i][j]] = cnt;
				cnt ++;
			}
			curr = mp[curr][text[i][j]];
		}
		fin[curr].push_back(i);
	}
}

void transform(string &str) {
	for(auto &it : str) {
		if(it == 'A') {
			it = 0;
		} else if(it == 'U') {
			it = 1;
		} else if(it == 'G') {
			it = 2;
		} else if(it == 'C') {
			it = 3;
		}
	}
}

Trie trie[MAX_N];
int who[MAX_N];

void dfsMerge(int x, int y, int ndx, int ndy) {
	if(ndy == -1) {return;}
	trie[x].nds[ndx].cnt += trie[y].nds[ndy].cnt;
	for(int i = 0; i < 4; i ++) {
		if(trie[y].nds[ndy].mp[i] == -1) {continue;}
		if(trie[x].nds[ndx].mp[i] == -1) {
			trie[x].nds[ndx].mp[i] = trie[x].size();
			trie[x].nds.push_back(Node());
		}
		dfsMerge(x, y, trie[x].nds[ndx].mp[i], trie[y].nds[ndy].mp[i]);
	}
}

void merge(int x, int y) {
	if(trie[who[x]].size() > trie[who[y]].size()) {
		swap(who[x], who[y]);
	}
	dfsMerge(who[x], who[y], 0, 0);
	trie[who[y]].nds.resize(0);
}

void dfs(int x) {
	for(auto it : fin[x]) {
		reverse(text[it].begin(), text[it].end());
		trie[who[x]].add(text[it]);
	}
	for(int i = 0; i < 4; i ++) {
		if(mp[x][i] == -1) {continue;}
		dfs(mp[x][i]);
		merge(x, mp[x][i]);
	}
	for(auto it : quer[x]) {
		ans[it] = trie[who[x]].cnt(in[it][1]);
	}
	return;
	cout << endl;
	trie[who[x]].outputtrie(0, {});
	cout << endl << endl;
}

void computeAns() {
	for(int i = 0; i < q; i ++) {
		int curr = 0;
		for(int j = 0; j < in[i][0].size(); j ++) {
			curr = mp[curr][in[i][0][j]];
			if(curr == -1) {
				break;
			}
		}
		if(curr == -1) {continue;}
		quer[curr].push_back(i);
	}
	dfs(0);
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	for(int i = 0; i < MAX_N; i ++) {
		for(int j = 0; j < 4; j ++) {
			mp[i][j] = -1;
		}
		who[i] = i;	
	}
	cin >> n >> q;
	for(int i = 0; i < n; i ++) {
		cin >> text[i];
		transform(text[i]);
	}
	buildTrie();
	for(int i = 0; i < q; i ++) {
		cin >> in[i][0] >> in[i][1];
		transform(in[i][0]);
		reverse(in[i][1].begin(), in[i][1].end());
		transform(in[i][1]);
	}
	computeAns();
	for(int i = 0; i < q; i ++) {
		cout << ans[i] << endl;
	}
	return 0;
}

Compilation message (stderr)

selling_rna.cpp: In member function 'void Trie::add(const string&)':
selling_rna.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for(int i = 0; i < str.size(); i ++) {
      |                  ~~^~~~~~~~~~~~
selling_rna.cpp:35:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   35 |    if(nds[curr].mp[str[i]] == -1) {
      |                          ^
selling_rna.cpp:36:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   36 |     nds[curr].mp[str[i]] = nds.size();
      |                        ^
selling_rna.cpp:39:30: warning: array subscript has type 'char' [-Wchar-subscripts]
   39 |    curr = nds[curr].mp[str[i]];
      |                              ^
selling_rna.cpp: In member function 'int Trie::cnt(const string&)':
selling_rna.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   for(int i = 0; i < str.size(); i ++) {
      |                  ~~^~~~~~~~~~~~
selling_rna.cpp:47:27: warning: array subscript has type 'char' [-Wchar-subscripts]
   47 |    curr = nds[i].mp[str[i]];
      |                           ^
selling_rna.cpp: In function 'void buildTrie()':
selling_rna.cpp:76:20: 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 < text[i].size(); j ++) {
      |                  ~~^~~~~~~~~~~~~~~~
selling_rna.cpp:77:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   77 |    if(mp[curr][text[i][j]] == -1) {
      |                          ^
selling_rna.cpp:78:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   78 |     mp[curr][text[i][j]] = cnt;
      |                        ^
selling_rna.cpp:81:30: warning: array subscript has type 'char' [-Wchar-subscripts]
   81 |    curr = mp[curr][text[i][j]];
      |                              ^
selling_rna.cpp: In function 'void computeAns()':
selling_rna.cpp:147:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |   for(int j = 0; j < in[i][0].size(); j ++) {
      |                  ~~^~~~~~~~~~~~~~~~~
selling_rna.cpp:148:31: warning: array subscript has type 'char' [-Wchar-subscripts]
  148 |    curr = mp[curr][in[i][0][j]];
      |                               ^

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