oj.uz

답안 #933049

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
933049 2024-02-24T23:30:23 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 503 ms 1048576 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -