oj.uz

답안 #859586

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
859586 2023-10-10T10:41:04 Z Hakiers Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 266248 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;
}

void addtrie(int v, string &t, string &r, 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], t, r, 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], t, r, itt, itr+1);
	}
		
}

void addcnt(int v, string &t, string &r, 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], t, r, 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], t, r, it+1, reversed);
		
	if(!reversed && 0 < r.size() && T[v][translate[(int)r[0]]][1] != -1)
		addcnt(T[v][translate[(int)r[0]]][1], t, r, 1, 1);
	
	
	
}

int res(int v, string &t, string &r, int itt, int itr){
	
	if(itt < t.size())
		return res(T[v][translate[(int)t[itt]]][0], t, r, itt+1, itr);
	else if(itr < r.size()) 
		return res(T[v][translate[(int)r[itr]]][1], t, r, 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 t;
		cin >> t;
		rna.push_back(t);
	}
	
	for(int i = 1; i <= m; i++){
		string t, w;
		cin >> t >> w;
		reverse(w.begin(), w.end());
		queries.push_back({t, w});
		addtrie(0, t, w, 0, 0);
	}
	
	for(auto t : rna){
		string r = t;
		reverse(r.begin(), r.end());
		addcnt(0, t, r, 0, 0);
	}
	
	for(auto [t, w]: queries)
		cout << res(0, t, w, 0, 0) << "\n";

}

Compilation message

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

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 251728 KB Output is correct
2 Correct 43 ms 251736 KB Output is correct
3 Correct 44 ms 251744 KB Output is correct
4 Correct 43 ms 251716 KB Output is correct
5 Correct 44 ms 251732 KB Output is correct
6 Correct 43 ms 251680 KB Output is correct
7 Correct 44 ms 251736 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 256340 KB Output is correct
2 Correct 89 ms 256460 KB Output is correct
3 Correct 81 ms 258488 KB Output is correct
4 Correct 83 ms 258508 KB Output is correct
5 Correct 73 ms 265312 KB Output is correct
6 Correct 73 ms 265420 KB Output is correct
7 Execution timed out 1557 ms 266248 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 258640 KB Output is correct
2 Correct 55 ms 254796 KB Output is correct
3 Correct 60 ms 258640 KB Output is correct
4 Correct 61 ms 258380 KB Output is correct
5 Correct 56 ms 254800 KB Output is correct
6 Correct 59 ms 257616 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 251728 KB Output is correct
2 Correct 43 ms 251736 KB Output is correct
3 Correct 44 ms 251744 KB Output is correct
4 Correct 43 ms 251716 KB Output is correct
5 Correct 44 ms 251732 KB Output is correct
6 Correct 43 ms 251680 KB Output is correct
7 Correct 44 ms 251736 KB Output is correct
8 Correct 78 ms 256340 KB Output is correct
9 Correct 89 ms 256460 KB Output is correct
10 Correct 81 ms 258488 KB Output is correct
11 Correct 83 ms 258508 KB Output is correct
12 Correct 73 ms 265312 KB Output is correct
13 Correct 73 ms 265420 KB Output is correct
14 Execution timed out 1557 ms 266248 KB Time limit exceeded
15 Halted 0 ms 0 KB -