Submission #87414

#	Time	Username	Problem	Language	Result	Execution time	Memory
87414		KLPP	Selling RNA Strands (JOI16_selling_rna)	C++14	10 / 100	1524 ms	473892 KiB

selling_rna

#include<iostream>
#include<vector>
#include<algorithm>
#include<stdio.h>
using namespace std;
#define MOD 1000000007
#define BASE 257
typedef long long int lld;
struct Trie{
	struct Trie *child[26];
	vector<int> end;
};
void insert(Trie *T,string s, int index){
	Trie *S=T;
	for(int i=0;i<s.length();i++){
		int u=s[i]-'A';
		if(!S->child[u]){
			S->child[u]=new Trie();
			for(int j=0;j<26;j++)S->child[u]->child[j]=NULL;
		}
		S=S->child[u];
	}
	S->end.push_back(index);
}
pair<int,int> Query1[1000000];
vector<int> EulerTour1;
pair<int,int> Query2[1000000];
vector<int> EulerTour2;
void DFS1(Trie *T){
	sort(T->end.begin(),T->end.end());
	for(int i=0;i<T->end.size();i++){
		if(T->end[i]<=0){
			Query1[-T->end[i]].first=EulerTour1.size();
		}else EulerTour1.push_back(T->end[i]-1);
		//cout<<T->end[i]<<" ";
	}
	//cout<<endl;
	for(int i=0;i<26;i++){
		if(T->child[i]){
			DFS1(T->child[i]);
		}
	}
	for(int i=0;i<T->end.size();i++){
		if(T->end[i]<=0){
			Query1[-T->end[i]].second=EulerTour1.size()-1;
		}
		//cout<<T->end[i]<<" ";
	}
}
void DFS2(Trie *T){
	sort(T->end.begin(),T->end.end());
	for(int i=0;i<T->end.size();i++){
		if(T->end[i]<=0){
			Query2[-T->end[i]].first=EulerTour2.size();
		}else EulerTour2.push_back(T->end[i]-1);
		//cout<<T->end[i]<<" ";
	}
	//cout<<endl;
	for(int i=0;i<26;i++){
		if(T->child[i]){
			DFS2(T->child[i]);
		}
	}
	for(int i=0;i<T->end.size();i++){
		if(T->end[i]<=0){
			Query2[-T->end[i]].second=EulerTour2.size()-1;
		}
		//cout<<T->end[i]<<" ";
	}
}
int main(){
	int n,m;
	cin>>n>>m;
	string arr[n];
	Trie *T=new Trie();
	for(int i=0;i<n;i++){
		cin>>arr[i];
		insert(T,arr[i],i+1);
	}
	string Queries1[m];
	string Queries2[m];
	for(int i=0;i<m;i++){
		cin>>Queries1[i]>>Queries2[i];
		insert(T,Queries1[i],-i);
	}
	DFS1(T);
	/*for(int i=0;i<n;i++){
		cout<<EulerTour1[i]<<endl;
	}
	for(int i=0;i<m;i++){
		cout<<Query1[i].first<<" "<<Query1[i].second<<endl;
	}*/
	T=new Trie();
	for(int i=0;i<n;i++){
		reverse(arr[i].begin(),arr[i].end());
		insert(T,arr[i],i+1);
	}
	for(int i=0;i<m;i++){
		reverse(Queries2[i].begin(),Queries2[i].end());
		insert(T,Queries2[i],-i);
	}
	DFS2(T);
	/*for(int i=0;i<m;i++){
		cout<<Query2[i].first<<" "<<Query2[i].second<<endl;
	}*/
	for(int i=0;i<m;i++){
		int ans=0;
		for(int j=Query1[i].first;j<=Query1[i].second;j++){
			for(int k=Query2[i].first;k<=Query2[i].second;k++){
				if(EulerTour1[j]==EulerTour2[k])ans++;
			}
		}
		cout<<ans<<endl;
	}
	//cout<<'G'-'A'<<endl;
	
	
	return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'void insert(Trie*, std::__cxx11::string, int)':
selling_rna.cpp:15:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<s.length();i++){
              ~^~~~~~~~~~~
selling_rna.cpp: In function 'void DFS1(Trie*)':
selling_rna.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<T->end.size();i++){
              ~^~~~~~~~~~~~~~
selling_rna.cpp:43:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<T->end.size();i++){
              ~^~~~~~~~~~~~~~
selling_rna.cpp: In function 'void DFS2(Trie*)':
selling_rna.cpp:52:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<T->end.size();i++){
              ~^~~~~~~~~~~~~~
selling_rna.cpp:64:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<T->end.size();i++){
              ~^~~~~~~~~~~~~~

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