Submission #40740

#	Time	Username	Problem	Language	Result	Execution time	Memory
40740		IvanC	Selling RNA Strands (JOI16_selling_rna)	C++14	0 / 100	1564 ms	125476 KiB

selling_rna

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN = (int)1e5 + 10;
const int MAXL = (int)2*1e6 + 10;
inline int get(char c){
	if(c == 'A') return 0;
	else if(c == 'G') return 1;
	else if(c == 'C') return 2;
	else return 3;
}
string S[MAXN],Q[MAXN];
int Trie[MAXL][4],SZ[MAXL],resposta[MAXN],Trie2[MAXL][4],qtd[MAXL],ptr,ptr2,N,M;
vector<int> folhas[MAXL],queries[MAXL];
vector<int> *cjt[MAXL];
void add_correct(int idx){
	int atual = 0;
	for(int i = 0;i<S[idx].size();i++){
		int c = get(S[idx][i]);
		if(Trie[atual][c]){
			atual = Trie[atual][c];
		}
		else{
			Trie[atual][c] = ++ptr;
			atual = Trie[atual][c];
		}
	}
	folhas[atual].push_back(idx);
}
void add_reverse(int idx){
	int atual = 0;
	for(int i = 0;i<S[idx].size();i++){
		int c = get(S[idx][i]);
		if(Trie2[atual][c]){
			atual = Trie2[atual][c];
		}
		else{
			Trie2[atual][c] = ++ptr2;
			atual = Trie2[atual][c];
		}
		qtd[atual]++;
	}
}
void remove_reverse(int idx){
	int atual = 0;
	for(int i = 0;i<S[idx].size();i++){
		int c = get(S[idx][i]);
		if(Trie2[atual][c]){
			atual = Trie2[atual][c];
		}
		qtd[atual]--;
	}
}
void query_add(int idx){
	int atual = 0;
	for(int i = 0;i<Q[idx].size();i++){
		int c = get(Q[idx][i]);
		if(Trie[atual][c]){
			atual = Trie[atual][c];
		}
		else{
			return;
		}
	}
	queries[atual].push_back(idx);
}
int query_reverse(int idx){
	int atual = 0;
	for(int i = 0;i<Q[idx].size();i++){
		int c = get(Q[idx][i]);
		if(Trie2[atual][c]){
			atual = Trie2[atual][c];
		}
		else{
			return 0;
		}
	}
	return qtd[atual];
}
void calc_sz(int v){
	for(int idx : folhas[v]){
		SZ[v] += (int)S[idx].size();
	}
	for(int i = 0;i<4;i++){
		if(!Trie[v][i]) continue;
		int u = Trie[v][i];
		calc_sz(u);
		SZ[v] += SZ[u];
	}
}
void dfs(int v,int keep){
	int mx = -1,big = -1;
	for(int i = 0;i<4;i++){
		if(!Trie[v][i]) continue;
		int u = Trie[v][i];
		if(SZ[u] > mx){
			mx = SZ[u];
			big = u;
		}
	}
	big = -1;
	for(int i = 0;i<4;i++){
		if(!Trie[v][i]) continue;
		int u = Trie[v][i];
		if(u == big) continue;
		dfs(u,0);
	}
	if(big != -1){
		dfs(big,1);
		cjt[v] = cjt[big];
		for(int idx : folhas[v]){
			cjt[v]->push_back(idx);
			add_reverse(idx);
		}
	}
	else{
		cjt[v] = new vector<int>();
		for(int idx : folhas[v]){
			cjt[v]->push_back(idx);
			add_reverse(idx);
		}
	}
	for(int i = 0;i<4;i++){
		if(!Trie[v][i]) continue;
		int u = Trie[v][i];
		if(u == big) continue;
		for(int idx : *cjt[u]){
			cjt[v]->push_back(idx);
			add_reverse(idx);
		}
	}
	for(int idx : queries[v]) resposta[idx] = query_reverse(idx);
	if(keep == 0){
		for(int idx : *cjt[v]){
			remove_reverse(idx);
		}
	}
}
int main(){
	cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);
	scanf("%d %d",&N,&M);
	for(int i = 1;i<=N;i++){
		cin >> S[i];
		add_correct(i);
		reverse(S[i].begin(),S[i].end());
	}
	for(int i = 1;i<=M;i++){
		cin >> Q[i];
		query_add(i);
		cin >> Q[i];
		reverse(Q[i].begin(),Q[i].end());
	}
	calc_sz(0);
	dfs(0,1);
	for(int i = 1;i<=M;i++){
		printf("%d\n",resposta[i]);
	}
	return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'void add_correct(int)':
selling_rna.cpp:18:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<S[idx].size();i++){
                 ^
selling_rna.cpp: In function 'void add_reverse(int)':
selling_rna.cpp:32:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<S[idx].size();i++){
                 ^
selling_rna.cpp: In function 'void remove_reverse(int)':
selling_rna.cpp:46:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<S[idx].size();i++){
                 ^
selling_rna.cpp: In function 'void query_add(int)':
selling_rna.cpp:56:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<Q[idx].size();i++){
                 ^
selling_rna.cpp: In function 'int query_reverse(int)':
selling_rna.cpp:69:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<Q[idx].size();i++){
                 ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:141:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&N,&M);
                      ^

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