oj.uz

Submission #48982

# Submission time Handle Problem Language Result Execution time Memory
48982 2018-05-21T06:05:16 Z Namnamseo Selling RNA Strands (JOI16_selling_rna) C++17
60 / 100
 1500 ms 217008 KB 
#include <bits/stdc++.h>
using namespace std;
#define sz(v) ((v).size())
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define coord_comp(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define v_index(v, x) (lower_bound(all(v),x)-(v).begin())
typedef pair<int,int> pp;
typedef long long ll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T1,typename T2>
void read(pair<T1,T2>& p){ read(p.first); read(p.second); }
template<typename T,typename... Args>
void read(T&a,Args&...b){ read(a); read(b...); }

inline int conv(char x){
	if(x=='A') return 0;
	if(x=='U') return 1;
	if(x=='G') return 2;
	if(x=='C') return 3;
	return 4;
}

struct node {
	node *p[5];
	node *fail;
	vector<int> term;
	node(){
		for(int i=0; i<5; ++i) p[i]=0;
		fail=0;
	}
	void put(int ind,char* cp){
		if((*cp) == 0){
			term.pb(ind);
			return;
		}
		int x=conv(*cp);
		if(!p[x]) p[x]=new node();
		p[x]->put(ind, cp+1);
	}
} *root;

int n,m;

string hay[100010];
string needle[100010][2];

void in(){
	read(n,m);
	char buf[200010];
	for(int i=1; i<=n; ++i){
		scanf("%s",buf); hay[i]=string(buf);
	}
	root = new node();
	for(int i=1; i<=m; ++i){
		scanf("%s",buf); needle[i][0]=string(buf);
		scanf("%s",buf); needle[i][1]=string(buf);
		int p=needle[i][0].length();
		int q=needle[i][1].length();
		for(int j=0; j<q; ++j) buf[j]=needle[i][1][j];
		buf[q] = '$';
		for(int j=0; j<p; ++j)
			buf[q+1+j]=needle[i][0][j];
		buf[p+q+1]=0;
		root->put(i, buf);
	}
}

void aho(){
	queue<node*> q;
	root->fail = root;
	for(int i=0; i<5; ++i){
		if(root->p[i]){
			root->p[i]->fail = root;
			q.push(root->p[i]);
		} else {
			root->p[i]=root;
		}
	}
	while(q.size()){
		node *m=q.front(); q.pop();
		for(int i=0;i<5;++i){
			auto n=m->p[i];
			if(n){
				auto tmp=m->fail;
				while(tmp!=root && !tmp->p[i]) tmp=tmp->fail;
				if(tmp->p[i]) tmp=tmp->p[i];
				n->fail = tmp;
				for(int t:tmp->term)
					n->term.pb(t);
				q.push(n);
			} else {
				auto tmp=m->fail;
				while(tmp!=root && !tmp->p[i]) tmp=tmp->fail;
				if(tmp->p[i]) tmp=tmp->p[i];
				m->p[i]=tmp;
			}
		}
	}
}

int ans[100010];

int main(){
	in();
	aho();
	for(int i=1; i<=n; ++i){
		string a=hay[i]+string("$")+hay[i];
		node *cur=root;
		for(char c : a){
			int x=conv(c);
			cur=cur->p[x];
			for(int t:cur->term) ++ans[t];
		}
	}
	for(int i=1; i<=m; ++i) printf("%d\n",ans[i]);
	return 0;
}

Compilation message

selling_rna.cpp: In function 'void read(int&)':
selling_rna.cpp:10:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(int& x){ scanf("%d",&x); }
                    ~~~~~^~~~~~~~~
selling_rna.cpp: In function 'void read(ll&)':
selling_rna.cpp:11:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(ll& x){ scanf("%lld",&x); }
                   ~~~~~^~~~~~~~~~~
selling_rna.cpp: In function 'void in()':
selling_rna.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",buf); hay[i]=string(buf);
   ~~~~~^~~~~~~~~~
selling_rna.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",buf); needle[i][0]=string(buf);
   ~~~~~^~~~~~~~~~
selling_rna.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",buf); needle[i][1]=string(buf);
   ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9848 KB Output is correct
2 Correct 9 ms 9848 KB Output is correct
3 Correct 9 ms 10016 KB Output is correct
4 Correct 10 ms 10200 KB Output is correct
5 Correct 9 ms 10200 KB Output is correct
6 Correct 9 ms 10200 KB Output is correct
7 Correct 9 ms 10296 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 33800 KB Output is correct
2 Correct 129 ms 33800 KB Output is correct
3 Correct 192 ms 76248 KB Output is correct
4 Correct 196 ms 80904 KB Output is correct
5 Correct 376 ms 129180 KB Output is correct
6 Correct 353 ms 130856 KB Output is correct
7 Correct 381 ms 146968 KB Output is correct
8 Correct 625 ms 183456 KB Output is correct
9 Correct 731 ms 217008 KB Output is correct
10 Correct 101 ms 217008 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1071 ms 217008 KB Output is correct
2 Correct 107 ms 217008 KB Output is correct
3 Correct 159 ms 217008 KB Output is correct
4 Correct 262 ms 217008 KB Output is correct
5 Correct 100 ms 217008 KB Output is correct
6 Correct 157 ms 217008 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9848 KB Output is correct
2 Correct 9 ms 9848 KB Output is correct
3 Correct 9 ms 10016 KB Output is correct
4 Correct 10 ms 10200 KB Output is correct
5 Correct 9 ms 10200 KB Output is correct
6 Correct 9 ms 10200 KB Output is correct
7 Correct 9 ms 10296 KB Output is correct
8 Correct 120 ms 33800 KB Output is correct
9 Correct 129 ms 33800 KB Output is correct
10 Correct 192 ms 76248 KB Output is correct
11 Correct 196 ms 80904 KB Output is correct
12 Correct 376 ms 129180 KB Output is correct
13 Correct 353 ms 130856 KB Output is correct
14 Correct 381 ms 146968 KB Output is correct
15 Correct 625 ms 183456 KB Output is correct
16 Correct 731 ms 217008 KB Output is correct
17 Correct 101 ms 217008 KB Output is correct
18 Correct 1071 ms 217008 KB Output is correct
19 Correct 107 ms 217008 KB Output is correct
20 Correct 159 ms 217008 KB Output is correct
21 Correct 262 ms 217008 KB Output is correct
22 Correct 100 ms 217008 KB Output is correct
23 Correct 157 ms 217008 KB Output is correct
24 Correct 300 ms 217008 KB Output is correct
25 Correct 269 ms 217008 KB Output is correct
26 Correct 158 ms 217008 KB Output is correct
27 Correct 165 ms 217008 KB Output is correct
28 Execution timed out 1572 ms 217008 KB Time limit exceeded
29 Halted 0 ms 0 KB -