oj.uz

Submission #87414

# Submission time Handle Problem Language Result Execution time Memory
87414 2018-11-30T18:30:30 Z KLPP Selling RNA Strands (JOI16_selling_rna) C++14
10 / 100
 1500 ms 473892 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#include<stdio.h>
using namespace std;
#define MOD 1000000007
#define BASE 257
typedef long long int lld;
struct Trie{
	struct Trie *child[26];
	vector<int> end;
};
void insert(Trie *T,string s, int index){
	Trie *S=T;
	for(int i=0;i<s.length();i++){
		int u=s[i]-'A';
		if(!S->child[u]){
			S->child[u]=new Trie();
			for(int j=0;j<26;j++)S->child[u]->child[j]=NULL;
		}
		S=S->child[u];
	}
	S->end.push_back(index);
}
pair<int,int> Query1[1000000];
vector<int> EulerTour1;
pair<int,int> Query2[1000000];
vector<int> EulerTour2;
void DFS1(Trie *T){
	sort(T->end.begin(),T->end.end());
	for(int i=0;i<T->end.size();i++){
		if(T->end[i]<=0){
			Query1[-T->end[i]].first=EulerTour1.size();
		}else EulerTour1.push_back(T->end[i]-1);
		//cout<<T->end[i]<<" ";
	}
	//cout<<endl;
	for(int i=0;i<26;i++){
		if(T->child[i]){
			DFS1(T->child[i]);
		}
	}
	for(int i=0;i<T->end.size();i++){
		if(T->end[i]<=0){
			Query1[-T->end[i]].second=EulerTour1.size()-1;
		}
		//cout<<T->end[i]<<" ";
	}
}
void DFS2(Trie *T){
	sort(T->end.begin(),T->end.end());
	for(int i=0;i<T->end.size();i++){
		if(T->end[i]<=0){
			Query2[-T->end[i]].first=EulerTour2.size();
		}else EulerTour2.push_back(T->end[i]-1);
		//cout<<T->end[i]<<" ";
	}
	//cout<<endl;
	for(int i=0;i<26;i++){
		if(T->child[i]){
			DFS2(T->child[i]);
		}
	}
	for(int i=0;i<T->end.size();i++){
		if(T->end[i]<=0){
			Query2[-T->end[i]].second=EulerTour2.size()-1;
		}
		//cout<<T->end[i]<<" ";
	}
}
int main(){
	int n,m;
	cin>>n>>m;
	string arr[n];
	Trie *T=new Trie();
	for(int i=0;i<n;i++){
		cin>>arr[i];
		insert(T,arr[i],i+1);
	}
	string Queries1[m];
	string Queries2[m];
	for(int i=0;i<m;i++){
		cin>>Queries1[i]>>Queries2[i];
		insert(T,Queries1[i],-i);
	}
	DFS1(T);
	/*for(int i=0;i<n;i++){
		cout<<EulerTour1[i]<<endl;
	}
	for(int i=0;i<m;i++){
		cout<<Query1[i].first<<" "<<Query1[i].second<<endl;
	}*/
	T=new Trie();
	for(int i=0;i<n;i++){
		reverse(arr[i].begin(),arr[i].end());
		insert(T,arr[i],i+1);
	}
	for(int i=0;i<m;i++){
		reverse(Queries2[i].begin(),Queries2[i].end());
		insert(T,Queries2[i],-i);
	}
	DFS2(T);
	/*for(int i=0;i<m;i++){
		cout<<Query2[i].first<<" "<<Query2[i].second<<endl;
	}*/
	for(int i=0;i<m;i++){
		int ans=0;
		for(int j=Query1[i].first;j<=Query1[i].second;j++){
			for(int k=Query2[i].first;k<=Query2[i].second;k++){
				if(EulerTour1[j]==EulerTour2[k])ans++;
			}
		}
		cout<<ans<<endl;
	}
	//cout<<'G'-'A'<<endl;
	
	
	return 0;
}

Compilation message

selling_rna.cpp: In function 'void insert(Trie*, std::__cxx11::string, int)':
selling_rna.cpp:15:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<s.length();i++){
              ~^~~~~~~~~~~
selling_rna.cpp: In function 'void DFS1(Trie*)':
selling_rna.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<T->end.size();i++){
              ~^~~~~~~~~~~~~~
selling_rna.cpp:43:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<T->end.size();i++){
              ~^~~~~~~~~~~~~~
selling_rna.cpp: In function 'void DFS2(Trie*)':
selling_rna.cpp:52:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<T->end.size();i++){
              ~^~~~~~~~~~~~~~
selling_rna.cpp:64:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<T->end.size();i++){
              ~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 552 KB Output is correct
3 Correct 3 ms 552 KB Output is correct
4 Correct 3 ms 572 KB Output is correct
5 Correct 3 ms 572 KB Output is correct
6 Correct 3 ms 572 KB Output is correct
7 Correct 3 ms 572 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1524 ms 473892 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1522 ms 473892 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 552 KB Output is correct
3 Correct 3 ms 552 KB Output is correct
4 Correct 3 ms 572 KB Output is correct
5 Correct 3 ms 572 KB Output is correct
6 Correct 3 ms 572 KB Output is correct
7 Correct 3 ms 572 KB Output is correct
8 Execution timed out 1524 ms 473892 KB Time limit exceeded
9 Halted 0 ms 0 KB -