oj.uz

답안 #633506

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
633506 2022-08-22T15:29:20 Z MatBad Dabbeh (INOI20_dabbeh) C++14
25 / 100
 270 ms 52616 KB 
#include<bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i=a; i<=b; i++)
#define FORR(i, a, b) for(int i=a; i>=b; i--)
#define pb push_back
#define ppb pop_back
#define lc 2*u
#define rc 2*u+1
#define mid ((l+r)/2)
#define F first
#define S second
#define debug(x) cerr<<"$ "<<#x<<" : "<<x<<"$\n"
#define wall() cerr<<"\n----------------------\n"

typedef long long ll;
typedef pair<int, int> pii;

const ll MX=505, M=5e5+5, LG=19, inf=1e9+5, MOD=1e9+7, A=27;

int m, n, tr[M][A], N, dp[MX][MX];
string s;

void add(string& t){
	int v=0;
	FOR(i, 0, (int)t.size()-1){
		if(!tr[v][t[i]-'a']) tr[v][t[i]-'a'] = ++N; 
		v = tr[v][t[i]-'a'];
	}
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m;
	FOR(i, 1, n){
		string t;
		cin>>t;
		add(t);
	}
	cin>>s;
	int L=s.size();
	FORR(i, L-1, 0) FOR(j, i, L-1){
		dp[i][j]=inf;
		for(int v=tr[0][s[i]-'a'], h=1; v!=0 and i+h<=L; v=tr[v][s[i+h]-'a'], h++){
			dp[i][j]=min(dp[i][j], 1+dp[i+h][j]);
		}
	}
	
	FOR(q, 1, m){
		int l, r;
		cin>>l>>r;
		r--;
		//l--; r--;
		cout<<(dp[l][r]==inf?-1:dp[l][r])<<'\n';
	}
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 82 ms 41152 KB Output is correct
3 Correct 81 ms 30464 KB Output is correct
4 Correct 84 ms 40508 KB Output is correct
5 Correct 82 ms 37184 KB Output is correct
6 Correct 87 ms 47128 KB Output is correct
7 Correct 92 ms 52616 KB Output is correct
8 Correct 91 ms 49972 KB Output is correct
9 Correct 91 ms 45180 KB Output is correct
10 Correct 69 ms 12264 KB Output is correct
11 Correct 270 ms 50200 KB Output is correct
12 Correct 236 ms 25996 KB Output is correct
13 Correct 239 ms 39528 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 28 ms 36564 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 82 ms 41152 KB Output is correct
3 Correct 81 ms 30464 KB Output is correct
4 Correct 84 ms 40508 KB Output is correct
5 Correct 82 ms 37184 KB Output is correct
6 Correct 87 ms 47128 KB Output is correct
7 Correct 92 ms 52616 KB Output is correct
8 Correct 91 ms 49972 KB Output is correct
9 Correct 91 ms 45180 KB Output is correct
10 Correct 69 ms 12264 KB Output is correct
11 Correct 270 ms 50200 KB Output is correct
12 Correct 236 ms 25996 KB Output is correct
13 Correct 239 ms 39528 KB Output is correct
14 Runtime error 28 ms 36564 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -