oj.uz

답안 #859567

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
859567 2023-10-10T10:21:36 Z Hakiers Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 271628 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 251784 KB Output is correct
3 Correct 47 ms 251988 KB Output is correct
4 Correct 44 ms 251728 KB Output is correct
5 Correct 44 ms 251732 KB Output is correct
6 Correct 49 ms 251764 KB Output is correct
7 Correct 43 ms 251732 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 260136 KB Output is correct
2 Correct 92 ms 260480 KB Output is correct
3 Correct 85 ms 262432 KB Output is correct
4 Correct 85 ms 262600 KB Output is correct
5 Correct 76 ms 267880 KB Output is correct
6 Correct 75 ms 267724 KB Output is correct
7 Execution timed out 1523 ms 271628 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 258772 KB Output is correct
2 Correct 58 ms 255184 KB Output is correct
3 Correct 60 ms 259424 KB Output is correct
4 Correct 56 ms 258636 KB Output is correct
5 Correct 57 ms 255088 KB Output is correct
6 Correct 60 ms 259100 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 251728 KB Output is correct
2 Correct 43 ms 251784 KB Output is correct
3 Correct 47 ms 251988 KB Output is correct
4 Correct 44 ms 251728 KB Output is correct
5 Correct 44 ms 251732 KB Output is correct
6 Correct 49 ms 251764 KB Output is correct
7 Correct 43 ms 251732 KB Output is correct
8 Correct 80 ms 260136 KB Output is correct
9 Correct 92 ms 260480 KB Output is correct
10 Correct 85 ms 262432 KB Output is correct
11 Correct 85 ms 262600 KB Output is correct
12 Correct 76 ms 267880 KB Output is correct
13 Correct 75 ms 267724 KB Output is correct
14 Execution timed out 1523 ms 271628 KB Time limit exceeded
15 Halted 0 ms 0 KB -