oj.uz

Submission #859584

# Submission time Handle Problem Language Result Execution time Memory
859584 2023-10-10T10:39:34 Z Hakiers Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 266172 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 8e6 + 7;
int T[MAXN][4][2];
int translate[200];
int cnt[MAXN][2];
vector<string> rna;
vector<pair<string ,string>> queries;
int wierzcholki = 0;
int n, m;

void trieinit(){
	for(int i = 0; i < MAXN; i++)
		for(int j = 0; j < 4; j++)
			T[i][j][0] = T[i][j][1] = -1;
			
	translate[(int)'A'] = 0;
	translate[(int)'G'] = 1;
	translate[(int)'C'] = 2;
	translate[(int)'U'] = 3;
}

string t, r;
void addtrie(int v, int itt, int itr){
	/*
	if(itr >= r.size()) return;
	
	if(T[v][translate[(int)t[itt]]][0] == -1 && itt < t.size())
		T[v][translate[(int)t[itt]]][0] = ++wierzcholki;
	else if(itt >= t.size() && T[v][translate[(int)r[itr]]][1] == -1)
		T[v][translate[(int)r[itr]]][1] = ++wierzcholki;
	
	
	if(itt < t.size())
		addtrie(T[v][translate[(int)t[itt]]][0], t, r, itt+1, itr);
	else addtrie(T[v][translate[(int)r[itr]]][1], t, r, itt, itr+1);
	*/
	
	
	if(itt < t.size()){
		if(T[v][translate[(int)t[itt]]][0] == -1)
			T[v][translate[(int)t[itt]]][0] = ++wierzcholki;
			
		addtrie(T[v][translate[(int)t[itt]]][0], itt+1, itr);
	}
	else if(itr < r.size()){
		if(T[v][translate[(int)r[itr]]][1] == -1)
			T[v][translate[(int)r[itr]]][1] = ++wierzcholki;
		addtrie(T[v][translate[(int)r[itr]]][1], itt, itr+1);
	}
		
}

void addcnt(int v, int it, bool reversed = 0){
	/*
	cnt[v][reversed]++;
	if(it >= r.size() && reversed) return;
	
	if(!reversed && T[v][translate[(int)r[0]]][1] != -1)
			addcnt(T[v][translate[(int)r[0]]][1], t, r, 1, 1);
	
	if(!reversed && T[v][translate[(int)t[it]]][0] != -1){
		addcnt(T[v][translate[(int)t[it]]][0], t, r, it+1, reversed);
	}
	else if(reversed && T[v][translate[(int)r[it]]][1] != -1)
		addcnt(T[v][translate[(int)r[it]]][1], t, r, it+1, reversed);
	*/
	cnt[v][reversed]++;
	
	if(!reversed && it < t.size() &&  T[v][translate[(int)t[it]]][0] != -1)
		addcnt(T[v][translate[(int)t[it]]][0], it+1, reversed);
	else if(reversed && it < r.size() && T[v][translate[(int)r[it]]][1] != -1)
		addcnt(T[v][translate[(int)r[it]]][1], it+1, reversed);
		
	if(!reversed && 0 < r.size() && T[v][translate[(int)r[0]]][1] != -1)
		addcnt(T[v][translate[(int)r[0]]][1], 1, 1);
	
	
	
}

int res(int v, int itt, int itr){
	
	if(itt < t.size())
		return res(T[v][translate[(int)t[itt]]][0], itt+1, itr);
	else if(itr < r.size()) 
		return res(T[v][translate[(int)r[itr]]][1], itt, itr+1);
	
	return cnt[v][1];
}


int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	trieinit();
	
	for(int i = 1; i <= n; i++){
		string x;
		cin >> x;
		rna.push_back(x);
	}
	
	for(int i = 1; i <= m; i++){
		cin >> t >> r;
		reverse(r.begin(), r.end());
		queries.push_back({t, r});
		addtrie(0, 0, 0);
	}
	
	for(auto x : rna){
		t = x;
		r = x;
		reverse(r.begin(), r.end());
		addcnt(0, 0, 0);
	}
	
	for(auto [l, k]: queries){
		t = l;
		r = k;
		cout << res(0, 0, 0) << "\n";
	}

}

Compilation message

selling_rna.cpp: In function 'void addtrie(int, int, int)':
selling_rna.cpp:40:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  if(itt < t.size()){
      |     ~~~~^~~~~~~~~~
selling_rna.cpp:46:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  else if(itr < r.size()){
      |          ~~~~^~~~~~~~~~
selling_rna.cpp: In function 'void addcnt(int, int, bool)':
selling_rna.cpp:70:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  if(!reversed && it < t.size() &&  T[v][translate[(int)t[it]]][0] != -1)
      |                  ~~~^~~~~~~~~~
selling_rna.cpp:72:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  else if(reversed && it < r.size() && T[v][translate[(int)r[it]]][1] != -1)
      |                      ~~~^~~~~~~~~~
selling_rna.cpp: In function 'int res(int, int, int)':
selling_rna.cpp:84:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |  if(itt < t.size())
      |     ~~~~^~~~~~~~~~
selling_rna.cpp:86:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  else if(itr < r.size())
      |          ~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 251728 KB Output is correct
2 Correct 44 ms 252240 KB Output is correct
3 Correct 48 ms 251728 KB Output is correct
4 Correct 45 ms 251796 KB Output is correct
5 Correct 43 ms 251812 KB Output is correct
6 Correct 44 ms 251732 KB Output is correct
7 Correct 44 ms 251728 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 256084 KB Output is correct
2 Correct 88 ms 256460 KB Output is correct
3 Correct 80 ms 258504 KB Output is correct
4 Correct 85 ms 258508 KB Output is correct
5 Correct 72 ms 265420 KB Output is correct
6 Correct 74 ms 265452 KB Output is correct
7 Execution timed out 1565 ms 266172 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 259152 KB Output is correct
2 Correct 56 ms 254876 KB Output is correct
3 Correct 59 ms 257700 KB Output is correct
4 Correct 58 ms 258124 KB Output is correct
5 Correct 56 ms 254780 KB Output is correct
6 Correct 63 ms 258200 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 251728 KB Output is correct
2 Correct 44 ms 252240 KB Output is correct
3 Correct 48 ms 251728 KB Output is correct
4 Correct 45 ms 251796 KB Output is correct
5 Correct 43 ms 251812 KB Output is correct
6 Correct 44 ms 251732 KB Output is correct
7 Correct 44 ms 251728 KB Output is correct
8 Correct 75 ms 256084 KB Output is correct
9 Correct 88 ms 256460 KB Output is correct
10 Correct 80 ms 258504 KB Output is correct
11 Correct 85 ms 258508 KB Output is correct
12 Correct 72 ms 265420 KB Output is correct
13 Correct 74 ms 265452 KB Output is correct
14 Execution timed out 1565 ms 266172 KB Time limit exceeded
15 Halted 0 ms 0 KB -