Submission #560676

#	Time	Username	Problem	Language	Result	Execution time	Memory
560676		MohamedAhmed04	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	280 ms	214724 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 2e6 + 10 ;

string arr[MAX] ;
int n , q ;

int getid[27] ;
int val[MAX] ;
int triesuff[MAX][5] , triepref[MAX][5] ;
vector<int>v[MAX] ;

int idsuff = 0 ;

void InsertSuff(string &s , int idx)
{
	int node = 0 ;
	for(int i = 0 ; i < s.size() ; ++i)
	{
		int c = getid[s[i] - 'A'] ;
		if(!triesuff[node][c])
			triesuff[node][c] = ++idsuff ;
		node = triesuff[node][c] ;
	}
	val[idx] = node ;
}

int in[MAX] , out[MAX] ;
int tim = 0 ;

void dfs(int node)
{
	in[node] = ++tim ;
	for(int c = 0 ; c < 4 ; ++c)
	{
		if(triesuff[node][c])
			dfs(triesuff[node][c]) ;
	}
	out[node] = tim ;
}

int idpref = 0 ;

void InsertPref(string &s , int idx)
{
	int node = 0 ;
	for(int i = 0 ; i < s.size() ; ++i)
	{
		int c = getid[s[i] - 'A'] ;
		if(!triepref[node][c])
			triepref[node][c] = ++idpref ;
		node = triepref[node][c] ;
		v[node].push_back(in[val[idx]]) ;
	}
}

int FindNode(string &s)
{
	int node = 0 ;
	for(int i = 0 ; i < s.size() ; ++i)
	{
		int c = getid[s[i] - 'A'] ;
		if(!triesuff[node][c])
			return -1 ;
		node = triesuff[node][c] ;
	}
	return node ;
}

int query(string &s , int x)
{
	if(x == -1)
		return 0 ;
	int node = 0 ;
	for(int i = 0 ; i < s.size() ; ++i)
	{
		int c = getid[s[i] - 'A'] ;
		if(!triepref[node][c])
			return 0 ;
		node = triepref[node][c] ;
	}
	int l = in[x] , r = out[x] ;
	return (upper_bound(v[node].begin() , v[node].end() , r) - lower_bound(v[node].begin() , v[node].end() , l)) ;
}


int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>q ;
	for(int i = 1 ; i <= n ; ++i)
		cin>>arr[i] ;
	getid['A' - 'A'] = 0 , getid['C' - 'A'] = 1 , getid['G' - 'A'] = 2 , getid['U' - 'A'] = 3 ;
	for(int i = 1 ; i <= n ; ++i)
	{
		reverse(arr[i].begin() , arr[i].end()) ;
		InsertSuff(arr[i] , i) ;
		reverse(arr[i].begin() , arr[i].end()) ;
	}
	dfs(0) ;
	for(int i = 1 ; i <= n ; ++i)
		InsertPref(arr[i] , i) ;
	for(int i = 0 ; i < MAX ; ++i)
		sort(v[i].begin() , v[i].end()) ;
	while(q--)
	{
		string s , t ;
		cin>>s>>t ;
		reverse(t.begin() , t.end()) ;
		int x = FindNode(t) ;
		cout<<query(s , x)<<"\n" ;
	}
	return 0 ;
}		

Compilation message (stderr)

selling_rna.cpp: In function 'void InsertSuff(std::string&, int)':
selling_rna.cpp:20:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i = 0 ; i < s.size() ; ++i)
      |                  ~~^~~~~~~~~~
selling_rna.cpp: In function 'void InsertPref(std::string&, int)':
selling_rna.cpp:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int i = 0 ; i < s.size() ; ++i)
      |                  ~~^~~~~~~~~~
selling_rna.cpp: In function 'int FindNode(std::string&)':
selling_rna.cpp:62:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for(int i = 0 ; i < s.size() ; ++i)
      |                  ~~^~~~~~~~~~
selling_rna.cpp: In function 'int query(std::string&, int)':
selling_rna.cpp:77:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for(int i = 0 ; i < s.size() ; ++i)
      |                  ~~^~~~~~~~~~

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