oj.uz

Submission #531470

# Submission time Handle Problem Language Result Execution time Memory
531470 2022-02-28T18:48:44 Z fcw Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 52908 KB 
#include <bits/stdc++.h>
#define st first
#define nd second
using lint = int64_t;
constexpr int mod = int(1e9) + 7;
constexpr int inf = 0x3f3f3f3f;
constexpr int ninf = 0xcfcfcfcf;
constexpr lint linf = 0x3f3f3f3f3f3f3f3f;
const long double pi = acosl(-1.0);
// Returns -1 if a < b, 0 if a = b and 1 if a > b.
int cmp_double(double a, double b = 0, double eps = 1e-9) {
	return a + eps > b ? b + eps > a ? 0 : 1 : -1;
}
using namespace std;

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

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n, m;
	cin>>n>>m;
	vector<string>s(n), t(n), p(m), q(m);
	for(int i=0;i<n;i++){
		cin>>s[i];
		t[i] = s[i];
		reverse(t[i].begin(), t[i].end());
	}
	for(int i=0;i<m;i++){
		cin>>p[i]>>q[i];
		reverse(q[i].begin(), q[i].end());
	}
	vector<array<int, 4>>triep(1, {-1, -1, -1, -1}), trieq(1, {-1, -1, -1, -1});
	vector<vector<int>>gp(1), gq(1);
	for(int i=0;i<m;i++){
		{
			int cur = 0;
			for(char c : p[i]){
				int b = f(c);
				if(triep[cur][b] == -1){
					triep[cur][b] = (int)triep.size();
					triep.push_back({-1, -1, -1, -1});
					gp.push_back({});
				}
				cur = triep[cur][b];
			}
			gp[cur].push_back(i);
		}
		{
			int cur = 0;
			for(char c : q[i]){
				int b = f(c);
				if(trieq[cur][b] == -1){
					trieq[cur][b] = (int)trieq.size();
					trieq.push_back({-1, -1, -1, -1});
					gq.push_back({});
				}
				cur = trieq[cur][b];
			}
			gq[cur].push_back(i);
		}
	}
	vector<int>ans(m);
	vector<bool>w(m);
	for(int i=0;i<n;i++){
		vector<int>v;
		{
			int cur = 0;
			for(char c : s[i]){
				int b = f(c);
				if(triep[cur][b] == -1) break;
				cur = triep[cur][b];
				for(int u : gp[cur]){
					v.push_back(u);
					w[u] = 1;
				}
			}
		}
		{
			int cur = 0;
			for(char c : t[i]){
				int b = f(c);
				if(trieq[cur][b] == -1) break;
				cur = trieq[cur][b];
				for(int u : gq[cur]){
					if(w[u]) ans[u]++;
				}
			}
		}
		for(int u : v) w[u] = 0;
	}
	for(int i=0;i<m;i++) cout<<ans[i]<<"\n";

	return 0;
}
/*
[  ]Leu o problema certo???
[  ]Ver se precisa de long long
[  ]Viu o limite dos fors (é n? é m?)
[  ]Tamanho do vetor, será que é 2e5 em vez de 1e5??
[  ]Testar sample
[  ]Testar casos de  borda
[  ]1LL no 1LL << i
[  ]Testar mod (é 1e9+7, mesmo?, será que o mod não ficou negativo?)
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 10844 KB Output is correct
2 Correct 147 ms 11284 KB Output is correct
3 Correct 92 ms 11064 KB Output is correct
4 Correct 113 ms 11240 KB Output is correct
5 Correct 66 ms 43340 KB Output is correct
6 Correct 68 ms 42880 KB Output is correct
7 Correct 155 ms 13772 KB Output is correct
8 Correct 87 ms 52908 KB Output is correct
9 Correct 96 ms 49388 KB Output is correct
10 Correct 341 ms 10224 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1575 ms 8044 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 53 ms 10844 KB Output is correct
9 Correct 147 ms 11284 KB Output is correct
10 Correct 92 ms 11064 KB Output is correct
11 Correct 113 ms 11240 KB Output is correct
12 Correct 66 ms 43340 KB Output is correct
13 Correct 68 ms 42880 KB Output is correct
14 Correct 155 ms 13772 KB Output is correct
15 Correct 87 ms 52908 KB Output is correct
16 Correct 96 ms 49388 KB Output is correct
17 Correct 341 ms 10224 KB Output is correct
18 Execution timed out 1575 ms 8044 KB Time limit exceeded
19 Halted 0 ms 0 KB -