Submission #634257

#	Time	Username	Problem	Language	Result	Execution time	Memory
634257		Mahdi	Dabbeh (INOI20_dabbeh)	C++17	50 / 100	2081 ms	192760 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef long long ll;
typedef pair<int, int> pii;
const int N=5e5+5, M=1e4+5;
int n, q, h, dis[N], nxt[N][28], C[N][28], f[N], p[N][22], ff[N];
vector<int>g[N];
string s[M], L;

void add(const string &t){
    int v=0;
    for(int i=0;i<t.size();++i){
        int z=t[i]-'a';
        if(nxt[v][z]==0){
            dis[h]=dis[v]+1;
            nxt[v][z]=h++;
        }
        v=nxt[v][z];
    }
}

int opr(const int &v, const int &x){
    if(nxt[v][x]!=0){
        C[v][x]=nxt[v][x];
        f[nxt[v][x]]=C[f[v]][x];
    }
    else
        C[v][x]=C[f[v]][x];
    return nxt[v][x];
}

void bfs(){
    vector<int>nd={0};
    f[0]=-1;
    for(int i=0;i<26;++i){
        if(nxt[0][i]!=0){
            C[0][i]=nxt[0][i];
            nd.push_back(nxt[0][i]);
        }
    }
    for(int i=1;i<nd.size();++i){
        int v=nd[i];
        for(int j=0;j<26;++j){
            int u=opr(v, j);
            if(u!=0)
                nd.push_back(u);
        }
    }
}

void dfs(const int &v){
    for(int u: g[v]){
        p[u][0]=v;
        for(int i=1;i<20;++i)
            p[u][i]=p[p[u][i-1]][i-1];
        dfs(u);
    }
}

int bin(int u, int h){
    if(dis[u]<=h)
        return dis[u];
    for(int i=19;i>=0;--i){
        if(dis[p[u][i]]>h)
            u=p[u][i];
    }
    return dis[p[u][0]];
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>q;
    h=1;
    for(int i=0;i<n;++i){
        cin>>s[i];
        add(s[i]);
    }
    bfs();
    for(int i=1;i<h;++i)
        g[f[i]].push_back(i);
    cin>>L;
    int v=0;
    for(int i=0;i<L.size();++i){
        v=C[v][L[i]-'a'];
        ff[i+1]=v;
    }
    dfs(0);
    while(q--){
        int l, r;
        cin>>l>>r;
        int ans=0;
        while(r>l){
            ++ans;
            int rr=bin(ff[r], r-l);
            if(rr==0){
                ans=-1;
                break;
            }
            r-=rr;
        }
        cout<<ans<<'\n';
    }
}

Compilation message (stderr)

Main.cpp: In function 'void add(const string&)':
Main.cpp:15:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int i=0;i<t.size();++i){
      |                 ~^~~~~~~~~
Main.cpp: In function 'void bfs()':
Main.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i=1;i<nd.size();++i){
      |                 ~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:86:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for(int i=0;i<L.size();++i){
      |                 ~^~~~~~~~~

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