Submission #921367

---

Source Code Expand

# include <stdio.h>
# include <bits/stdc++.h>
using namespace std;
# define fi cin
# define fo cout
# define x first
# define y second
# define ll long long
# define IOS ios_base :: sync_with_stdio(0);cin.tie(0)
# define p(v) cerr << #v << " = " << v << '\n'
# define p2(v) cerr << #v << " = " << (complex < int > (v.x,v.y)) << '\n'
# define vi vector < int >
# define vll vector < ll >
# define pii pair < int , int >
# define mp make_pair
int dp[1 << 17][26][26];
int nxt[1 << 19][26];
int sum[1 << 19];
int name[1 << 19];
int cur = 0;
void add(string s,int N)
{
    int cnt = 0;
    for (auto it : s)
    {
        const int w = it - 'a';
        if (!nxt[cnt][w]) nxt[cnt][w] = ++cur;
        cnt = nxt[cnt][w];
        ++sum[cnt];
    }
    name[cnt] = N;
}
int C[55][55];
int W[1 << 20];
void dfs(int node = 0,int add = 0)
{
    for (int i = 0;i < 26;++i)
        if (nxt[node][i])
        {
            for (int j = 0;j < 26;++j)
                if (nxt[node][j] && i != j)
                    C[i][j] += sum[nxt[node][j]];
            dfs(nxt[node][i],(name[node] != 0) + add);
            for (int j = 0;j < 26;++j)
                if (nxt[node][j] && i != j)
                    C[i][j] -= sum[nxt[node][j]];
        }
    if (name[node])
    {
        for (int i = 0;i < 26;++i)
            for (int j = 0;j < 26;++j)
                dp[name[node]][i][j] = C[i][j];
        W[name[node]] = add;
    }
}
int main(void)
{
    #ifdef CF
    freopen("input","r",stdin);
    #endif // CF
    srand(time(0));
    fo << fixed << setprecision(7);
    cerr << fixed << setprecision(7);
    int n;
    fi>>n;
    for (int i = 1;i <= n;++i)
    {
        string s;
        fi>>s;
        add(s,i);
    }
    int m;
    dfs();
    fi>>m;
    for (int i = 1;i <= m;++i)
    {
        int k;
        fi>>k;
        string s;
        fi>>s;
        int ans = W[k] + 1;
        for (int i = 0;i < 26;++i)
            for (int j = i + 1;j < 26;++j)
                ans += dp[k][s[j] - 'a'][s[i] - 'a'];
        fo << ans << '\n';
    }
    cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
    return 0;
}

Submission Info

Judge Result