oj.uz

Submission #560676

# Submission time Handle Problem Language Result Execution time Memory
560676 2022-05-11T21:13:44 Z MohamedAhmed04 Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 280 ms 214724 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 109856 KB Output is correct
2 Correct 53 ms 109904 KB Output is correct
3 Correct 52 ms 109904 KB Output is correct
4 Correct 53 ms 109916 KB Output is correct
5 Correct 53 ms 109888 KB Output is correct
6 Correct 54 ms 110008 KB Output is correct
7 Correct 55 ms 109940 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 181820 KB Output is correct
2 Correct 274 ms 178872 KB Output is correct
3 Correct 243 ms 214724 KB Output is correct
4 Correct 227 ms 209996 KB Output is correct
5 Correct 205 ms 208992 KB Output is correct
6 Correct 205 ms 210596 KB Output is correct
7 Correct 124 ms 125496 KB Output is correct
8 Correct 230 ms 179764 KB Output is correct
9 Correct 229 ms 169896 KB Output is correct
10 Correct 216 ms 166632 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 111440 KB Output is correct
2 Correct 77 ms 111168 KB Output is correct
3 Correct 79 ms 111324 KB Output is correct
4 Correct 81 ms 111212 KB Output is correct
5 Correct 75 ms 111316 KB Output is correct
6 Correct 78 ms 111404 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 109856 KB Output is correct
2 Correct 53 ms 109904 KB Output is correct
3 Correct 52 ms 109904 KB Output is correct
4 Correct 53 ms 109916 KB Output is correct
5 Correct 53 ms 109888 KB Output is correct
6 Correct 54 ms 110008 KB Output is correct
7 Correct 55 ms 109940 KB Output is correct
8 Correct 245 ms 181820 KB Output is correct
9 Correct 274 ms 178872 KB Output is correct
10 Correct 243 ms 214724 KB Output is correct
11 Correct 227 ms 209996 KB Output is correct
12 Correct 205 ms 208992 KB Output is correct
13 Correct 205 ms 210596 KB Output is correct
14 Correct 124 ms 125496 KB Output is correct
15 Correct 230 ms 179764 KB Output is correct
16 Correct 229 ms 169896 KB Output is correct
17 Correct 216 ms 166632 KB Output is correct
18 Correct 73 ms 111440 KB Output is correct
19 Correct 77 ms 111168 KB Output is correct
20 Correct 79 ms 111324 KB Output is correct
21 Correct 81 ms 111212 KB Output is correct
22 Correct 75 ms 111316 KB Output is correct
23 Correct 78 ms 111404 KB Output is correct
24 Correct 258 ms 171460 KB Output is correct
25 Correct 280 ms 171780 KB Output is correct
26 Correct 248 ms 171152 KB Output is correct
27 Correct 200 ms 197096 KB Output is correct
28 Correct 265 ms 132752 KB Output is correct
29 Correct 132 ms 118996 KB Output is correct