Submission #921539
Source Code Expand
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> //#include<cctype> #include<climits> #include<iostream> #include<string> #include<vector> #include<map> //#include<list> #include<queue> #include<deque> #include<algorithm> //#include<numeric> #include<utility> //#include<memory> #include<functional> #include<cassert> #include<set> #include<stack> #include<random> const int dx[] = {1, 0, -1, 0}; const int dy[] = {0, -1, 0, 1}; using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> vi; typedef vector<ll> vll; typedef pair<int, int> pii; const int MAXN = 100100; string S[MAXN]; struct Node { int sum; int id; int child[26]; Node() : sum(0), id(-1) { memset(child, -1, sizeof(child)); } }; int trieNum = 1; Node trie[4*MAXN]; void addTrie(int from, int num) { if (trie[from].child[num] == -1) trie[from].child[num] = trieNum++; } int cnt[26][26]; int ans[MAXN][26][26]; int pf[MAXN]; void calc(int now, int p) { if (trie[now].id >= 0) { int id = trie[now].id; pf[id] = p++; for (int i = 0; i < 26; i++) { for (int j = 0; j < 26; j++) ans[id][i][j] = cnt[i][j]; } } for (int i = 0; i < 26; i++) { if (trie[now].child[i] >= 0) { for (int j = 0; j < 26; j++) { if (i != j && trie[now].child[j] >= 0) { int id = trie[now].child[j]; cnt[i][j] += trie[id].sum; } } calc(trie[now].child[i], p); for (int j = 0; j < 26; j++) { if (i != j && trie[now].child[j] >= 0) { int id = trie[now].child[j]; cnt[i][j] -= trie[id].sum; } } } } } int pos[26]; int main() { cin.tie(0); ios::sync_with_stdio(false); int N, Q; cin >> N; for (int i = 0; i < N; i++) { cin >> S[i]; int now = 0; for (char c : S[i]) { trie[now].sum++; addTrie(now, c-'a'); now = trie[now].child[c-'a']; } trie[now].sum++; trie[now].id = i; } calc(0, 0); cin >> Q; while (Q--) { int k; string perm; cin >> k >> perm; --k; for (int i = 0; i < 26; i++) pos[perm[i]-'a'] = i; int res = 1 + pf[k]; for (int i = 0; i < 26; i++) { for (int j = 0; j < 26; j++) { if (pos[i] > pos[j]) res += ans[k][i][j]; } } cout << res << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Lexicographical disorder |
User | mayoko |
Language | C++14 (GCC 5.4.1) |
Score | 1100 |
Code Size | 2761 Byte |
Status | AC |
Exec Time | 1207 ms |
Memory | 314496 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 | 1187 ms | 314496 KB |
02.txt | AC | 1202 ms | 314496 KB |
03.txt | AC | 1195 ms | 314496 KB |
04.txt | AC | 1207 ms | 314496 KB |
05.txt | AC | 1001 ms | 153088 KB |
06.txt | AC | 852 ms | 56448 KB |
07.txt | AC | 841 ms | 48384 KB |
08.txt | AC | 841 ms | 46208 KB |
09.txt | AC | 830 ms | 46208 KB |
10.txt | AC | 846 ms | 50384 KB |
11.txt | AC | 916 ms | 126336 KB |
12.txt | AC | 961 ms | 162944 KB |
13.txt | AC | 1023 ms | 204544 KB |
14.txt | AC | 843 ms | 56448 KB |
15.txt | AC | 829 ms | 46208 KB |
16.txt | AC | 832 ms | 50384 KB |
17.txt | AC | 857 ms | 64284 KB |
18.txt | AC | 771 ms | 48000 KB |
19.txt | AC | 773 ms | 48000 KB |
20.txt | AC | 780 ms | 48000 KB |
21.txt | AC | 768 ms | 48000 KB |
22.txt | AC | 767 ms | 48000 KB |
23.txt | AC | 950 ms | 150016 KB |
24.txt | AC | 897 ms | 125056 KB |
25.txt | AC | 960 ms | 161664 KB |
26.txt | AC | 776 ms | 48000 KB |
27.txt | AC | 792 ms | 56192 KB |
28.txt | AC | 798 ms | 60544 KB |
29.txt | AC | 773 ms | 47104 KB |
30.txt | AC | 860 ms | 93952 KB |
31.txt | AC | 795 ms | 48896 KB |
32.txt | AC | 783 ms | 46336 KB |
33.txt | AC | 789 ms | 47872 KB |
34.txt | AC | 785 ms | 47104 KB |
35.txt | AC | 794 ms | 46464 KB |
36.txt | AC | 1189 ms | 314496 KB |
37.txt | AC | 811 ms | 55060 KB |
38.txt | AC | 813 ms | 55060 KB |
39.txt | AC | 55 ms | 44928 KB |
40.txt | AC | 55 ms | 44800 KB |
s1.txt | AC | 54 ms | 44800 KB |
s2.txt | AC | 54 ms | 44928 KB |