oj.uz

Submission #954433

# Submission time Handle Problem Language Result Execution time Memory
954433 2024-03-27T21:37:35 Z amirhoseinfar1385 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 185 ms 292280 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[maxm],insy[maxm];
	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 102 ms 279800 KB Output is correct
2 Correct 100 ms 279736 KB Output is correct
3 Correct 102 ms 279764 KB Output is correct
4 Correct 103 ms 280044 KB Output is correct
5 Correct 101 ms 279888 KB Output is correct
6 Correct 104 ms 279888 KB Output is correct
7 Correct 108 ms 279888 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 287140 KB Output is correct
2 Correct 148 ms 286968 KB Output is correct
3 Correct 174 ms 284752 KB Output is correct
4 Correct 175 ms 288376 KB Output is correct
5 Correct 172 ms 285464 KB Output is correct
6 Correct 170 ms 285488 KB Output is correct
7 Correct 142 ms 291408 KB Output is correct
8 Correct 169 ms 292280 KB Output is correct
9 Correct 169 ms 292256 KB Output is correct
10 Correct 142 ms 287112 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 280912 KB Output is correct
2 Correct 114 ms 280404 KB Output is correct
3 Correct 113 ms 280720 KB Output is correct
4 Correct 111 ms 280548 KB Output is correct
5 Correct 113 ms 280400 KB Output is correct
6 Correct 116 ms 280620 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 279800 KB Output is correct
2 Correct 100 ms 279736 KB Output is correct
3 Correct 102 ms 279764 KB Output is correct
4 Correct 103 ms 280044 KB Output is correct
5 Correct 101 ms 279888 KB Output is correct
6 Correct 104 ms 279888 KB Output is correct
7 Correct 108 ms 279888 KB Output is correct
8 Correct 137 ms 287140 KB Output is correct
9 Correct 148 ms 286968 KB Output is correct
10 Correct 174 ms 284752 KB Output is correct
11 Correct 175 ms 288376 KB Output is correct
12 Correct 172 ms 285464 KB Output is correct
13 Correct 170 ms 285488 KB Output is correct
14 Correct 142 ms 291408 KB Output is correct
15 Correct 169 ms 292280 KB Output is correct
16 Correct 169 ms 292256 KB Output is correct
17 Correct 142 ms 287112 KB Output is correct
18 Correct 115 ms 280912 KB Output is correct
19 Correct 114 ms 280404 KB Output is correct
20 Correct 113 ms 280720 KB Output is correct
21 Correct 111 ms 280548 KB Output is correct
22 Correct 113 ms 280400 KB Output is correct
23 Correct 116 ms 280620 KB Output is correct
24 Correct 150 ms 288940 KB Output is correct
25 Correct 155 ms 289620 KB Output is correct
26 Correct 147 ms 288664 KB Output is correct
27 Correct 185 ms 289008 KB Output is correct
28 Correct 181 ms 291900 KB Output is correct
29 Correct 146 ms 285012 KB Output is correct