oj.uz

Submission #197724

# Submission time Handle Problem Language Result Execution time Memory
197724 2020-01-22T14:11:57 Z TAISA_ Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 408 ms 238200 KB 
#include<bits/stdc++.h>
#define all(v) v.begin(),v.end()
using namespace std;
using ll=long long;
using vi=vector<ll>;
using P=pair<int,int>;
int idx[26];
struct Node{
	char c;
	int idx,out;
	Node* to[4];
	vector<int> vs;
	Node(char cc){
		c=cc;
		idx=-1;
		out=-1;
		for(int i=0;i<4;i++){
			to[i]=nullptr;
		}
	}
};
struct Trie{
	Node* rt;
	Trie(){
		rt=new Node('Z');
	}
	Node* insert(string& s,int t){
		Node* now=rt;
		for(int i=0;i<s.length();i++){
			Node* par=now;
			now=par->to[idx[s[i]-'A']];
			if(now==nullptr){
				now=new Node(s[i]);
				par->to[idx[s[i]-'A']]=now;
			}
			if(t!=-1){
				now->vs.emplace_back(t);
			}
		}
		return now;
	}
	int etour(Node* now,int id=-1){
		now->idx=id;
		for(int i=0;i<4;i++){
			if(now->to[i]!=nullptr){
				int to=etour(now->to[i],id+1);
				id=to;
			}
		}
		now->out=id;
		return id;
	}
};
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	idx[0]=0;
	idx[2]=1;
	idx['G'-'A']=2;
	idx['U'-'A']=3;
	int n,m;cin>>n>>m;
	vector<string> s(n),p(m),q(m);
	Trie pre,suf;
	vector<Node*> en(m),nds(n);
	vector<P> vv;
	for(int i=0;i<n;i++){
		cin>>s[i];
		nds[i]=pre.insert(s[i],-1);
	}
	for(int i=0;i<m;i++){
		cin>>p[i]>>q[i];
		reverse(all(q[i]));
		en[i]=pre.insert(p[i],-1);
	}
	pre.etour(pre.rt);
	for(int i=0;i<n;i++){
		vv.emplace_back(P(nds[i]->idx,i));
	}
	sort(all(vv));
	for(int id=0;id<n;id++){
		int i=vv[id].second;
		reverse(all(s[i]));
		suf.insert(s[i],vv[id].first);
	}
	for(int i=0;i<m;i++){
		Node* nd=suf.insert(q[i],-1);
		int ub=en[i]->out,lb=en[i]->idx;
		int res=upper_bound(all(nd->vs),ub)-lower_bound(all(nd->vs),lb);
		cout<<res<<'\n';
	}
}

Compilation message

selling_rna.cpp: In member function 'Node* Trie::insert(std::__cxx11::string&, int)':
selling_rna.cpp:29:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<s.length();i++){
               ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 14 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 248 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 224764 KB Output is correct
2 Correct 327 ms 213332 KB Output is correct
3 Correct 337 ms 172384 KB Output is correct
4 Correct 314 ms 164600 KB Output is correct
5 Correct 396 ms 234772 KB Output is correct
6 Correct 408 ms 238200 KB Output is correct
7 Correct 130 ms 20600 KB Output is correct
8 Correct 378 ms 153144 KB Output is correct
9 Correct 331 ms 130960 KB Output is correct
10 Correct 234 ms 122588 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 7668 KB Output is correct
2 Correct 29 ms 5360 KB Output is correct
3 Correct 34 ms 6512 KB Output is correct
4 Correct 25 ms 5364 KB Output is correct
5 Correct 29 ms 5364 KB Output is correct
6 Correct 34 ms 6384 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 14 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 248 KB Output is correct
8 Correct 336 ms 224764 KB Output is correct
9 Correct 327 ms 213332 KB Output is correct
10 Correct 337 ms 172384 KB Output is correct
11 Correct 314 ms 164600 KB Output is correct
12 Correct 396 ms 234772 KB Output is correct
13 Correct 408 ms 238200 KB Output is correct
14 Correct 130 ms 20600 KB Output is correct
15 Correct 378 ms 153144 KB Output is correct
16 Correct 331 ms 130960 KB Output is correct
17 Correct 234 ms 122588 KB Output is correct
18 Correct 35 ms 7668 KB Output is correct
19 Correct 29 ms 5360 KB Output is correct
20 Correct 34 ms 6512 KB Output is correct
21 Correct 25 ms 5364 KB Output is correct
22 Correct 29 ms 5364 KB Output is correct
23 Correct 34 ms 6384 KB Output is correct
24 Correct 304 ms 186908 KB Output is correct
25 Correct 323 ms 189684 KB Output is correct
26 Correct 298 ms 184056 KB Output is correct
27 Correct 301 ms 145144 KB Output is correct
28 Correct 217 ms 53656 KB Output is correct
29 Correct 112 ms 20820 KB Output is correct