Submission #1265817

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265817		mhn_neek	Dabbeh (INOI20_dabbeh)	C++20	25 / 100	2096 ms	106632 KiB

Main

//In the name of God
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef pair<lli,lli> pii;
typedef vector<lli> ve;
typedef vector<pii> vp;
const lli N = 5e5 + 100;
const lli mod = 1e9 + 7;
const lli INF = 1e18;
#define PB push_back
#define MP make_pair
#define fi first
#define se second
#define FOR(x,y) for(lli x = 0 ;x < y; x++)
#define FORS(x,y) for(lli x = 1 ;x <= y; x++)
#define debug(x) cerr<<(#x)<<" "<<x<<endl
#define all(x) x.begin(),x.end()

struct Trie{
	lli nxt[N][26];
	void build(){
		FOR(i,N)FOR(j,26)nxt[i][j] = -1;
	}
	lli vercnt = 1;
	void add(string s){
		lli v = 1;
		FOR(i,(lli)s.size()){
			if(nxt[v][(s[i]-'a')] == -1)
				nxt[v][(s[i]-'a')] = ++vercnt;		
			v = nxt[v][(s[i]-'a')];
		}
	}
	bool find(string s){
		lli v = 1;
		FOR(i,(lli)s.size()){
			if(nxt[v][(s[i]-'a')] == -1)return 0;
			v = nxt[v][(s[i]-'a')];
		}
		return 1;
	}
};
Trie t;
lli n,m;

lli dp[1000][1000];bool fo[1000][1000];


int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	t.build();
	FORS(i,n){
		string s;
		cin>>s;
		t.add(s);
	}
	string S;
	cin>>S;
	S = '#' + S;
	lli L = S.size()-1;
	FORS(l,L){
		string s = "";
		for(lli r = l;r <= L ;r ++){
			s += S[r];
			fo[l][r] = t.find(s);
		}
	}
	FORS(l,L){
		for(lli r = l; r <= L; r ++){
			dp[l][r] = INF;
			if(fo[l][r])dp[l][r] = 1;
		}
	}
	for(lli l = L; l > 0;  l --){
		for(lli r = l; r <=L; r ++){
			for(lli k = l; k < r; k ++)
				if(fo[l][k])
					dp[l][r] = min(dp[l][r],dp[k+1][r] + 1);
		}
	}
	while(m --){
		lli l,r;
		cin>>l>>r;
		l ++;
		if(dp[l][r] == INF)dp[l][r] = -1;
		cout<<dp[l][r]<<endl;
	}

}

• Subtask 1: 25 / 25
• Subtask 2: 0 / 25
• Subtask 3: 0 / 50