oj.uz

Submission #40742

# Submission time Handle Problem Language Result Execution time Memory
40742 2018-02-07T23:13:24 Z IvanC Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 369 ms 205308 KB 
#include <bits/stdc++.h>
using namespace std;
typedef vector<int>::iterator vit;
const int MAXN = (int)1e5 + 10;
const int MAXL = (int)2*1e6 + 10;
vector<int> queries[MAXL],folhas[MAXL];
vector<int> *cjt[MAXL];
string S[MAXN],Q[MAXN];
int Trie1[MAXL][4],Trie2[MAXL][4],ptr1,ptr2;
int resposta[MAXN],sz[MAXL],qtd[MAXL],N,M;
inline int transforma(char c){
	if(c == 'A') return 0;
	else if(c == 'G') return 1;
	else if(c == 'C') return 2;
	else return 3;
}
void add_reverse(int idx){
	int atual = 1;
	for(int i = 0;i<S[idx].size();i++){
		int c = transforma(S[idx][i]);
		if(Trie2[atual][c]){
			atual = Trie2[atual][c];
		}
		else{
			Trie2[atual][c] = ++ptr2;
			atual = ptr2;
		}
		qtd[atual]++;
	}
}
void remove_reverse(int idx){
	int atual = 1;
	for(int i = 0;i<S[idx].size();i++){
		int c = transforma(S[idx][i]);
		atual = Trie2[atual][c];
		qtd[atual]--;
	}
}
void add_normal(int idx){
	int atual = 1;
	for(int i = 0;i<S[idx].size();i++){
		int c = transforma(S[idx][i]);
		if(Trie1[atual][c]){
			atual = Trie1[atual][c];
		}
		else{
			Trie1[atual][c] = ++ptr1;
			atual = ptr1;
		}
		sz[atual] += (int)S[idx].size();
	}
	folhas[atual].push_back(idx);
}
int query_reverse(int idx){
	int atual = 1;
	for(int i = 0;i<Q[idx].size();i++){
		int c = transforma(Q[idx][i]);
		atual = Trie2[atual][c];
	} 
	return qtd[atual];
}
void add_query(int idx){
	int atual = 1;
	for(int i = 0;i<Q[idx].size();i++){
		int c = transforma(Q[idx][i]);
		atual = Trie1[atual][c];
	}
	queries[atual].push_back(idx);
}
void dfs(int v,int keep){
	int mx = -1,big = -1;
	for(int i = 0;i<4;i++){
		int u = Trie1[v][i];
		if(!u) continue;
		if(sz[u] > mx){
			big = u;
			mx = sz[u];
		}
	}
	for(int i = 0;i<4;i++){
		int u = Trie1[v][i];
		if(!u || u == big) continue;
		dfs(u,0);
	}
	if(big != -1){
		dfs(big,1);
		cjt[v] = cjt[big];
		for(vit it = folhas[v].begin();it != folhas[v].end();it++){
			add_reverse(*it);
			cjt[v]->push_back(*it);
		}
	}
	else{
		cjt[v] = new vector<int>();
		for(vit it = folhas[v].begin();it != folhas[v].end();it++){
			add_reverse(*it);
			cjt[v]->push_back(*it);
		}
	}
	for(int i = 0;i<4;i++){
		int u = Trie1[v][i];
		if(!u || u == big) continue;
		for(vit it = cjt[u]->begin();it != cjt[u]->end();it++){
			add_reverse(*it);
			cjt[v]->push_back(*it);
		}
	}
	for(vit it = queries[v].begin();it != queries[v].end();it++) resposta[*it] = query_reverse(*it);
	if(keep == 0){
		for(vit it = cjt[v]->begin();it != cjt[v]->end();it++){
			remove_reverse(*it);
		}
	}
}
int main(){
	cin.tie(0);ios_base::sync_with_stdio(0);
	cin >> N >> M;
	ptr1 = ptr2 = 1;
	for(int i = 1;i<=N;i++){
		cin >> S[i];
		add_normal(i);
		reverse(S[i].begin(),S[i].end());
	}
	for(int i = 1;i<=M;i++){
		cin >> Q[i];
		add_query(i);
		cin >> Q[i];
		reverse(Q[i].begin(),Q[i].end());
	}
	dfs(1,1);
	for(int i = 1;i<=M;i++) printf("%d\n",resposta[i]);
	return 0;
}

Compilation message

selling_rna.cpp: In function 'void add_reverse(int)':
selling_rna.cpp:19:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<S[idx].size();i++){
                 ^
selling_rna.cpp: In function 'void remove_reverse(int)':
selling_rna.cpp:33:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<S[idx].size();i++){
                 ^
selling_rna.cpp: In function 'void add_normal(int)':
selling_rna.cpp:41:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<S[idx].size();i++){
                 ^
selling_rna.cpp: In function 'int query_reverse(int)':
selling_rna.cpp:56:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<Q[idx].size();i++){
                 ^
selling_rna.cpp: In function 'void add_query(int)':
selling_rna.cpp:64:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<Q[idx].size();i++){
                 ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 100600 KB Output is correct
2 Correct 82 ms 100704 KB Output is correct
3 Correct 80 ms 100812 KB Output is correct
4 Correct 80 ms 100812 KB Output is correct
5 Correct 81 ms 100812 KB Output is correct
6 Correct 80 ms 100836 KB Output is correct
7 Correct 80 ms 101048 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 144312 KB Output is correct
2 Correct 177 ms 146388 KB Output is correct
3 Correct 330 ms 166848 KB Output is correct
4 Correct 325 ms 168220 KB Output is correct
5 Correct 324 ms 175548 KB Output is correct
6 Correct 330 ms 178984 KB Output is correct
7 Correct 122 ms 178984 KB Output is correct
8 Correct 214 ms 178984 KB Output is correct
9 Correct 199 ms 178984 KB Output is correct
10 Correct 215 ms 178984 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 178984 KB Output is correct
2 Correct 96 ms 178984 KB Output is correct
3 Correct 104 ms 178984 KB Output is correct
4 Correct 97 ms 178984 KB Output is correct
5 Correct 99 ms 178984 KB Output is correct
6 Correct 101 ms 178984 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 100600 KB Output is correct
2 Correct 82 ms 100704 KB Output is correct
3 Correct 80 ms 100812 KB Output is correct
4 Correct 80 ms 100812 KB Output is correct
5 Correct 81 ms 100812 KB Output is correct
6 Correct 80 ms 100836 KB Output is correct
7 Correct 80 ms 101048 KB Output is correct
8 Correct 171 ms 144312 KB Output is correct
9 Correct 177 ms 146388 KB Output is correct
10 Correct 330 ms 166848 KB Output is correct
11 Correct 325 ms 168220 KB Output is correct
12 Correct 324 ms 175548 KB Output is correct
13 Correct 330 ms 178984 KB Output is correct
14 Correct 122 ms 178984 KB Output is correct
15 Correct 214 ms 178984 KB Output is correct
16 Correct 199 ms 178984 KB Output is correct
17 Correct 215 ms 178984 KB Output is correct
18 Correct 100 ms 178984 KB Output is correct
19 Correct 96 ms 178984 KB Output is correct
20 Correct 104 ms 178984 KB Output is correct
21 Correct 97 ms 178984 KB Output is correct
22 Correct 99 ms 178984 KB Output is correct
23 Correct 101 ms 178984 KB Output is correct
24 Correct 184 ms 181068 KB Output is correct
25 Correct 196 ms 185900 KB Output is correct
26 Correct 181 ms 188540 KB Output is correct
27 Correct 369 ms 205308 KB Output is correct
28 Correct 222 ms 205308 KB Output is correct
29 Correct 162 ms 205308 KB Output is correct