oj.uz

Submission #954432

# Submission time Handle Problem Language Result Execution time Memory
954432 2024-03-27T21:36:39 Z amirhoseinfar1385 Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 220 ms 303152 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10,K=5,maxm=3000000+10;
int res[maxn],n,q;
string alls[maxn];
pair<string,string>allq[maxn];

struct triecnt{
	struct node{
		int allc[K],w;
		node(){
			w=0;
			allc[0]=allc[1]=allc[2]=allc[3]=allc[4]=-1;
		}
	};
	node tr[maxm];
	int te=1;
	void ins(string &s){
		int u=0;
		for(int i=0;i<(int)s.size();i++){
			int v=s[i]-'0';
			if(tr[u].allc[v]==-1){
				tr[u].allc[v]=te;
				te++;
			}
			u=tr[u].allc[v];
			tr[u].w++;
		}
	}
	int pors(string &s){
		int u=0;
		for(int i=0;i<(int)s.size();i++){
			int v=s[i]-'0';
			if(tr[u].allc[v]==-1){
				return 0;
			}
			u=tr[u].allc[v];
		}
		return tr[u].w;
	}
}trcnt;

struct trie{
	struct node{
		int allc[K];
		node(){
			allc[0]=allc[1]=allc[2]=allc[3]=allc[4]=-1;
		}
	};
	vector<int>qu[maxn],insy[maxn];
	node tr[maxm];
	int te=1;
	void ins(string &s,int ind){
		int u=0;
		for(int i=0;i<(int)s.size();i++){
			int v=s[i]-'0';
			if(tr[u].allc[v]==-1){
				tr[u].allc[v]=te;
				te++;
			}
			u=tr[u].allc[v];
		}
		insy[u].push_back(ind);
	}
	void cal(string &s,int ind){
		int u=0;
		for(int i=0;i<(int)s.size();i++){
			int v=s[i]-'0';
			if(tr[u].allc[v]==-1){
				return ;
			}
			u=tr[u].allc[v];
		}
		qu[u].push_back(ind);
	}
	void calres(int u=0){
		if(u==-1){
			return ;
		}
		for(auto x:qu[u]){
			string fs=allq[x].second;
			reverse(fs.begin(),fs.end());
			res[x]=-trcnt.pors(fs);
			//cout<<"av: "<<u<<" "<<x<<" "<<res[x]<<endl;
		}
		for(auto x:insy[u]){
			string fs=alls[x];
			reverse(fs.begin(),fs.end());
			trcnt.ins(fs);
		}
		for(int i=0;i<5;i++){
			if(tr[u].allc[i]!=-1)
			//cout<<u<<" "<<tr[u].allc[i]<<endl;
			calres(tr[u].allc[i]);
		}
		for(auto x:qu[u]){
			string fs=allq[x].second;
			reverse(fs.begin(),fs.end());
			res[x]+=trcnt.pors(fs);
			//cout<<"dov: "<<u<<" "<<x<<" "<<res[x]<<endl;
		}
	}
}tri;

void tagh(string &s){
	for(int i=0;i<(int)s.size();i++){
		if(s[i]=='A'){
			s[i]='0';
		}else if(s[i]=='G'){
			s[i]='1';
		}else if(s[i]=='C'){
			s[i]='2';
		}else{
			s[i]='3';
		}
	}
}

void vorod(){
	cin>>n>>q;
	for(int i=0;i<n;i++){
		cin>>alls[i];
		tagh(alls[i]);
	}
	for(int i=0;i<q;i++){
		cin>>allq[i].first>>allq[i].second;
		tagh(allq[i].first);
		tagh(allq[i].second);
	}
}

void pre(){
	for(int i=0;i<n;i++){
		tri.ins(alls[i],i);
	}
	for(int i=0;i<q;i++){
		tri.cal(allq[i].first,i);
	}
	tri.calres();
}

void khor(){
	for(int i=0;i<q;i++){
		cout<<res[i]<<"\n";
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//cout.tie(0);
	//freopen("inp.txt","r",stdin);
	vorod();
	pre();
	khor();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 143444 KB Output is correct
2 Correct 43 ms 143444 KB Output is correct
3 Correct 43 ms 143692 KB Output is correct
4 Correct 42 ms 143588 KB Output is correct
5 Correct 42 ms 143700 KB Output is correct
6 Correct 42 ms 143564 KB Output is correct
7 Correct 41 ms 143636 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 152660 KB Output is correct
2 Correct 80 ms 152288 KB Output is correct
3 Runtime error 220 ms 303152 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 144980 KB Output is correct
2 Correct 60 ms 144776 KB Output is correct
3 Correct 59 ms 144888 KB Output is correct
4 Correct 55 ms 144720 KB Output is correct
5 Correct 56 ms 144440 KB Output is correct
6 Correct 57 ms 144756 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 143444 KB Output is correct
2 Correct 43 ms 143444 KB Output is correct
3 Correct 43 ms 143692 KB Output is correct
4 Correct 42 ms 143588 KB Output is correct
5 Correct 42 ms 143700 KB Output is correct
6 Correct 42 ms 143564 KB Output is correct
7 Correct 41 ms 143636 KB Output is correct
8 Correct 79 ms 152660 KB Output is correct
9 Correct 80 ms 152288 KB Output is correct
10 Runtime error 220 ms 303152 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -