oj.uz

Submission #1045576

# Submission time Handle Problem Language Result Execution time Memory
1045576 2024-08-06T05:53:54 Z javotaz Dabbeh (INOI20_dabbeh) C++17
25 / 100
 105 ms 51536 KB 
// In the Name of Allah
 
#include<bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("Ofast,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,avx,avx2,sse4.2,popcnt,tune=native")
 
typedef long long ll;
 
#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
#define pp pop_back
#define all(x) x.begin(), x.end()

const int N = 503, M = 1e4 + 7, K = 5e5 + 7;
string s, a[M];
int n, q, dp[N][N], c, t[K][26], m;

void add(int id) {
	int p = 0;
	for (int i = 0; i < a[id].size(); i++) {
		if (!t[p][a[id][i] - 'a'])
			t[p][a[id][i] - 'a'] = ++c;
		p = t[p][a[id][i] - 'a'];
	}
}

void ip() {
	cin >> n >> q;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		add(i);
	}
	cin >> s;
	m = s.size();
}

void solve() {
	for (int d = 1; d <= m; d++)
		for (int l = 0; l + d <= m; l++) {
			int r = l + d;
			dp[l][r] = m + 1;
			for (int i = l, p = 0; i < r && (p = t[p][s[i] - 'a']); i++)
				dp[l][r] = min(dp[l][r], 1 + dp[i + 1][r]);
		}
	while (q--) {
		int l, r;
		cin >> l >> r;
		cout << ((dp[l][r] == m + 1)? -1 : dp[l][r]) << '\n';
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ip(), solve();
	return 0;
}

Compilation message

Main.cpp: In function 'void add(int)':
Main.cpp:24:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for (int i = 0; i < a[id].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 44 ms 40272 KB Output is correct
3 Correct 45 ms 29860 KB Output is correct
4 Correct 56 ms 39788 KB Output is correct
5 Correct 47 ms 36556 KB Output is correct
6 Correct 51 ms 46164 KB Output is correct
7 Correct 51 ms 51536 KB Output is correct
8 Correct 54 ms 51536 KB Output is correct
9 Correct 51 ms 46928 KB Output is correct
10 Correct 41 ms 14416 KB Output is correct
11 Correct 100 ms 49640 KB Output is correct
12 Correct 105 ms 25820 KB Output is correct
13 Correct 104 ms 38888 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 38328 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 44 ms 40272 KB Output is correct
3 Correct 45 ms 29860 KB Output is correct
4 Correct 56 ms 39788 KB Output is correct
5 Correct 47 ms 36556 KB Output is correct
6 Correct 51 ms 46164 KB Output is correct
7 Correct 51 ms 51536 KB Output is correct
8 Correct 54 ms 51536 KB Output is correct
9 Correct 51 ms 46928 KB Output is correct
10 Correct 41 ms 14416 KB Output is correct
11 Correct 100 ms 49640 KB Output is correct
12 Correct 105 ms 25820 KB Output is correct
13 Correct 104 ms 38888 KB Output is correct
14 Runtime error 19 ms 38328 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -