oj.uz

Submission #112378

# Submission time Handle Problem Language Result Execution time Memory
112378 2019-05-19T07:16:47 Z Mahdi_Jfri Selling RNA Strands (JOI16_selling_rna) C++14
0 / 100
 134 ms 68436 KB 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back

const int maxn = 1e5 + 20;
const int maxm = 2e6 + 20;
const int maxs = 5;

vector<pair<int , int> > query[maxn];

string s[maxn] , a[maxn] , b[maxn];

int nxt[maxm][maxs] , mx[maxm] , sz[maxm] , id = 1 , res[maxn];

void add(int ind)
{
	int p = 0;
	for(auto ch : s[ind])
	{
		if(!nxt[p][ch])
			nxt[p][ch] = id++;

		mx[p] = ind;
		sz[p]++;
		p = nxt[p][ch];
	}

	mx[p] = ind;
	sz[p]++;
}

pair<int , int> fn(string s)
{
	int p = 0;
	for(auto ch : s)
	{
		if(!nxt[p][ch])
			return make_pair(0 , 0);

		p = nxt[p][ch];
	}

	return {mx[p] , sz[p]};
}

void reval(string &s)
{
	for(auto &ch : s)
	{
		if(ch == 'A')
			ch = 0;
		else if(ch == 'G')
			ch = 1;
		else if(ch == 'C')
			ch = 2;
		else
			ch = 3;
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n , q;
	cin >> n >> q;

	for(int i = 1; i <= n; i++)
		cin >> s[i];
	sort(s + 1 , s + n + 1);

	for(int i = 1; i <= n; i++)
		add(i);

	assert(sz[0] == n);

	for(int i = 0; i < q; i++)
	{
		cin >> a[i] >> b[i];
		reverse(b[i].begin() , b[i].end());

		auto tmp = fn(a[i]);
		int r = tmp.first , l = tmp.first - tmp.second;
		query[r].pb({i , 1});
		query[l].pb({i ,-1});
	}

	memset(nxt , 0 , sizeof nxt);
	memset(mx , 0 , sizeof mx);
	memset(sz , 0 , sizeof sz);
	id = 1;

	for(int i = 1; i <= n; i++)
	{
		reverse(s[i].begin() , s[i].end());
		add(i);
		assert(sz[0] == i);

		for(auto tmp : query[i])
			res[tmp.first] += tmp.second * fn(b[tmp.first]).second;
	}

	for(int i = 0; i < q; i++)
		cout << res[i] << endl;
}

Compilation message

selling_rna.cpp: In function 'void add(int)':
selling_rna.cpp:22:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   if(!nxt[p][ch])
                ^
selling_rna.cpp:23:13: warning: array subscript has type 'char' [-Wchar-subscripts]
    nxt[p][ch] = id++;
             ^
selling_rna.cpp:27:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   p = nxt[p][ch];
                ^
selling_rna.cpp: In function 'std::pair<int, int> fn(std::__cxx11::string)':
selling_rna.cpp:39:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   if(!nxt[p][ch])
                ^
selling_rna.cpp:42:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   p = nxt[p][ch];
                ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 66936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 28792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 68436 KB Output is correct
2 Incorrect 103 ms 67952 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 66936 KB Output isn't correct
2 Halted 0 ms 0 KB -