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
Submission Time | |
---|---|
Task | E - Lexicographical disorder |
User | reality |
Language | C++14 (GCC 5.4.1) |
Score | 1100 |
Code Size | 2217 Byte |
Status | AC |
Exec Time | 1165 ms |
Memory | 275328 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1100 / 1100 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | s1.txt, s2.txt |
All | 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, s1.txt, s2.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01.txt | AC | 1148 ms | 275328 KB |
02.txt | AC | 1165 ms | 275328 KB |
03.txt | AC | 1148 ms | 275328 KB |
04.txt | AC | 1162 ms | 275328 KB |
05.txt | AC | 1006 ms | 138880 KB |
06.txt | AC | 866 ms | 54144 KB |
07.txt | AC | 841 ms | 46848 KB |
08.txt | AC | 836 ms | 44160 KB |
09.txt | AC | 830 ms | 43648 KB |
10.txt | AC | 839 ms | 49008 KB |
11.txt | AC | 871 ms | 83584 KB |
12.txt | AC | 937 ms | 120960 KB |
13.txt | AC | 993 ms | 163584 KB |
14.txt | AC | 868 ms | 52096 KB |
15.txt | AC | 830 ms | 43520 KB |
16.txt | AC | 831 ms | 49008 KB |
17.txt | AC | 856 ms | 67700 KB |
18.txt | AC | 736 ms | 3200 KB |
19.txt | AC | 716 ms | 3200 KB |
20.txt | AC | 716 ms | 3200 KB |
21.txt | AC | 712 ms | 3200 KB |
22.txt | AC | 709 ms | 3200 KB |
23.txt | AC | 917 ms | 110848 KB |
24.txt | AC | 861 ms | 82432 KB |
25.txt | AC | 922 ms | 119808 KB |
26.txt | AC | 707 ms | 3200 KB |
27.txt | AC | 754 ms | 15360 KB |
28.txt | AC | 752 ms | 21248 KB |
29.txt | AC | 731 ms | 8064 KB |
30.txt | AC | 841 ms | 57856 KB |
31.txt | AC | 759 ms | 17280 KB |
32.txt | AC | 723 ms | 10240 KB |
33.txt | AC | 740 ms | 18560 KB |
34.txt | AC | 736 ms | 15232 KB |
35.txt | AC | 758 ms | 18688 KB |
36.txt | AC | 1144 ms | 274048 KB |
37.txt | AC | 783 ms | 34232 KB |
38.txt | AC | 775 ms | 34232 KB |
39.txt | AC | 3 ms | 256 KB |
40.txt | AC | 3 ms | 256 KB |
s1.txt | AC | 3 ms | 256 KB |
s2.txt | AC | 3 ms | 256 KB |