Submission #933049

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
933049	2024-02-24T23:30:23 Z	vjudge1	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	503 ms	1048576 KB

selling_rna

#include <bits/stdc++.h>
#define endl "\n"
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repa(a,b) for(auto a:b)
#define pii pair<int, int>
#define fi first
#define se second
#define ll long long

using namespace std;

const int lim=1e5+5;

struct trie{
	trie *nxt[4]{};
	bool us=false;
	bitset<lim> bt;
} *pref, *suff;

int mp(char c){
	if(c=='A') return 0;
	if(c=='C') return 1;
	if(c=='G') return 2;
	return 3;
}

void add(string s, int p, int x, bool B){
	if(p&1){
		trie *act=pref;
		rep(i,0,s.size()){
			int nx=mp(s[i]);
			if(act->nxt[nx]==NULL) act->nxt[nx]=new trie;
			act=act->nxt[nx];
			if(B && act->us) act->bt.set(x);
		}
	}else{
		trie *act=suff;
		rep(i,0,s.size()){
			int nx=mp(s[i]);
			if(act->nxt[nx]==NULL) act->nxt[nx]=new trie;
			act=act->nxt[nx];
			if(B && act->us) act->bt.set(x);
		}
	}
}

void actv(string s, int p){
	if(p&1){
		trie *act=pref;
		rep(i,0,s.size()){
			int nx=mp(s[i]);
			if(act->nxt[nx]==NULL) return;
			act=act->nxt[nx];
		}
		act->us=true;
	}else{
		trie *act=suff;
		rep(i,0,s.size()){
			int nx=mp(s[i]);
			if(act->nxt[nx]==NULL) return;
			act=act->nxt[nx];
		}
		act->us=true;
	}
}

int query(string a, string b){
	trie *bg=pref, *ed=suff;
	rep(i,0,a.size()){
		int nx=mp(a[i]);
		if(bg->nxt[nx]==NULL) return 0;
		bg=bg->nxt[nx];
	}
	rep(i,0,b.size()){
		int nx=mp(b[i]);
		if(ed->nxt[nx]==NULL) return 0;
		ed=ed->nxt[nx];
	}
	return ((bg->bt)&(ed->bt)).count();
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, q;
	string a[n], s;
	cin>>n>>q;
	pref=new trie;
	suff=new trie;
	rep(i,0,n){
		cin>>a[i];
		s=a[i];
		add(s,1,i,0);
		reverse(s.begin(),s.end());
		add(s,2,i,0);
	}
	pair<string, string> qry[q];
	rep(i,0,q){
		cin>>qry[i].fi>>qry[i].se;
		reverse(qry[i].se.begin(),qry[i].se.end());
		actv(qry[i].fi,1);
		actv(qry[i].se,2);
	}
	rep(i,0,n){
		s=a[i];
		add(s,1,i,1);
		reverse(s.begin(),s.end());
		add(s,2,i,1);
	}
	rep(i,0,q){
		cout<<query(qry[i].fi,qry[i].se)<<endl;
	}
}

Compilation message

selling_rna.cpp: In function 'void add(std::string, int, int, bool)':
selling_rna.cpp:3:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define rep(a,b,c) for(int a=b; a<c; a++)
......
   30 |   rep(i,0,s.size()){
      |       ~~~~~~~~~~~~                
selling_rna.cpp:30:3: note: in expansion of macro 'rep'
   30 |   rep(i,0,s.size()){
      |   ^~~
selling_rna.cpp:3:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define rep(a,b,c) for(int a=b; a<c; a++)
......
   38 |   rep(i,0,s.size()){
      |       ~~~~~~~~~~~~                
selling_rna.cpp:38:3: note: in expansion of macro 'rep'
   38 |   rep(i,0,s.size()){
      |   ^~~
selling_rna.cpp: In function 'void actv(std::string, int)':
selling_rna.cpp:3:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define rep(a,b,c) for(int a=b; a<c; a++)
......
   50 |   rep(i,0,s.size()){
      |       ~~~~~~~~~~~~                
selling_rna.cpp:50:3: note: in expansion of macro 'rep'
   50 |   rep(i,0,s.size()){
      |   ^~~
selling_rna.cpp:3:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define rep(a,b,c) for(int a=b; a<c; a++)
......
   58 |   rep(i,0,s.size()){
      |       ~~~~~~~~~~~~                
selling_rna.cpp:58:3: note: in expansion of macro 'rep'
   58 |   rep(i,0,s.size()){
      |   ^~~
selling_rna.cpp: In function 'int query(std::string, std::string)':
selling_rna.cpp:3:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define rep(a,b,c) for(int a=b; a<c; a++)
......
   69 |  rep(i,0,a.size()){
      |      ~~~~~~~~~~~~                 
selling_rna.cpp:69:2: note: in expansion of macro 'rep'
   69 |  rep(i,0,a.size()){
      |  ^~~
selling_rna.cpp:3:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define rep(a,b,c) for(int a=b; a<c; a++)
......
   74 |  rep(i,0,b.size()){
      |      ~~~~~~~~~~~~                 
selling_rna.cpp:74:2: note: in expansion of macro 'rep'
   74 |  rep(i,0,b.size()){
      |  ^~~

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	90 ms	144964 KB	Output is correct
2	Correct	89 ms	144876 KB	Output is correct
3	Correct	87 ms	145268 KB	Output is correct
4	Correct	91 ms	144652 KB	Output is correct
5	Correct	88 ms	144976 KB	Output is correct
6	Correct	88 ms	144596 KB	Output is correct
7	Correct	88 ms	145004 KB	Output is correct

Subtask #2

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	503 ms	1048576 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #3

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	314 ms	145492 KB	Output is correct
2	Correct	245 ms	206076 KB	Output is correct
3	Correct	281 ms	178332 KB	Output is correct
4	Correct	251 ms	144464 KB	Output is correct
5	Correct	243 ms	204276 KB	Output is correct
6	Correct	281 ms	179168 KB	Output is correct

Subtask #4

0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	90 ms	144964 KB	Output is correct
2	Correct	89 ms	144876 KB	Output is correct
3	Correct	87 ms	145268 KB	Output is correct
4	Correct	91 ms	144652 KB	Output is correct
5	Correct	88 ms	144976 KB	Output is correct
6	Correct	88 ms	144596 KB	Output is correct
7	Correct	88 ms	145004 KB	Output is correct
8	Runtime error	503 ms	1048576 KB	Execution killed with signal 9
9	Halted	0 ms	0 KB	-