Submission #1655865

---

Source Code Expand

#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890123456789LL
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) ((x < 0)?-(x):x)
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

typedef long long cat;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

struct trie {
	vector< vector<int> > son;
	vector<int> SZ, ends;

	trie() {
		son.push_back(vector<int>(26,-1));
		SZ.resize(1);
		ends.resize(1,-1);
	}

	void put(string &S, int id) {
		int akt =0;
		for(int i =0; i < (int)S.length(); i++) {
			if(son[akt][S[i]-'a'] == -1) {
				son[akt][S[i]-'a'] =son.size();
				son.push_back(vector<int>(26,-1));
				SZ.push_back(0);
				ends.push_back(-1);
			}
			akt =son[akt][S[i]-'a'];
		}
		ends[akt] =id;
	}

	void DFS(int R) {
		SZ[R] =(ends[R] != -1);
		for(int i =0; i < 26; i++) if(son[R][i] != -1) {
			DFS(son[R][i]);
			SZ[R] +=SZ[son[R][i]];
		}
	}

	vector< vector<int> > sum;
	int sum0;

	void solve(int R, auto &Qs, auto &P, auto &ans) {
		if(ends[R] != -1) ALL_THE(Qs[ends[R]],it) {
			for(int i =0; i < 26; i++) for(int j =0; j < i; j++)
				ans[*it] +=sum[P[*it][i]-'a'][P[*it][j]-'a'];
			ans[*it] +=sum0;
		}

		if(ends[R] != -1) sum0++;
		for(int i =0; i < 26; i++) if(son[R][i] != -1) {
			for(int j =0; j < 26; j++) if(son[R][j] != -1 && i != j)
				sum[i][j] +=SZ[son[R][j]];
			solve(son[R][i],Qs,P,ans);
			for(int j =0; j < 26; j++) if(son[R][j] != -1 && i != j)
				sum[i][j] -=SZ[son[R][j]];
		}
		if(ends[R] != -1) sum0--;
	}
};

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int N;
	cin >> N;
	trie T;
	for(int i =0; i < N; i++) {
		string S;
		cin >> S;
		T.put(S,i);
	}
	T.DFS(0);

	int Q;
	cin >> Q;
	vector<string> P(Q);
	vector< vector<int> > Qs(N);
	for(int i =0; i < Q; i++) {
		int k;
		cin >> k >> P[i];
		Qs[k-1].push_back(i);
	}
	vector<int> ans(Q,1);

	T.sum =vector< vector<int> >(26,vector<int>(26,0));
	T.sum0 =0;
	T.solve(0,Qs,P,ans);

	for(int i =0; i < Q; i++) cout << ans[i] << "\n";
	return 0;}

// look at my code
// my code is amazing

Submission Info

Judge Result