Submission #921386
Source Code Expand
#include <iostream> #include <iomanip> #include <vector> #include <algorithm> #include <numeric> #include <functional> #include <cmath> #include <queue> #include <stack> #include <set> #include <map> #include <sstream> #include <string> #define repd(i,a,b) for (int i=(int)(a);i<(int)(b);i++) #define rep(i,n) repd(i,0,n) #define all(x) (x).begin(),(x).end() #define mod 1000000007 #define inf 2000000007 #define mp make_pair #define pb push_back typedef long long ll; using namespace std; template <typename T> inline void output(T a, int p = 0) { if(p) cout << fixed << setprecision(p) << a << "\n"; else cout << a << "\n"; } // end of template // Trie tree (Prefix tree) struct node{ node *next[26] = {}; int len[26] = {}; bool ok = false; int exist = 0; int num = 0; node() { rep(i, 26) len[i] = 1; } }; class Trie{ public: node *root; Trie(){ root = new node(); } void add(string &s){ node *cur = root; for(char &c : s){ if(!cur->next[c - 'a']){ cur->next[c - 'a'] = new node(); cur->exist++; } cur = cur->next[c - 'a']; } cur->ok = true; cur->num++; } // 縮約パート lenはその子のノードが何文字分縮約されているかを表す。numはcount(下参照) int dfs(node *n){ if(!n) return 0; rep(i, 26){ while(n->next[i] && n->next[i]->exist == 1 && !n->next[i]->ok){ rep(j, 26){ if(n->next[i]->next[j]){ n->next[i] = n->next[i]->next[j]; n->len[i]++; break; } } } n->num += dfs(n->next[i]); } return n->num; } // ノードnの子に登録した文字列(のprefix)がいくつあるかを数える int count(node *n){ return n ? n -> num : 0; } // 辞書順がlで定義された時のsの順番 int ord(string &s, string &l){ node *cur = root; int ret = 0; for(int i = 0; i < s.size();){ char c = s[i]; ret += cur->ok; rep(j, l.size()){ if(c == l[j]){ i += cur->len[c - 'a']; cur = cur->next[c - 'a']; break; } else{ ret += count(cur->next[l[j] - 'a']); } } } return ret; } }; int main() { cin.tie(0); ios::sync_with_stdio(0); // source code int N; cin >> N; vector<string> S(N); rep(i, N) cin >> S[i]; Trie trie; rep(i, N) trie.add(S[i]); trie.dfs(trie.root); int Q; cin >> Q; rep(i, Q){ int k; string s; cin >> k >> s; k--; output(trie.ord(S[k], s) + 1); } return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Lexicographical disorder |
User | ctyl |
Language | C++14 (GCC 5.4.1) |
Score | 1100 |
Code Size | 3132 Byte |
Status | AC |
Exec Time | 1887 ms |
Memory | 132480 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 | 170 ms | 39168 KB |
02.txt | AC | 170 ms | 39168 KB |
03.txt | AC | 168 ms | 39168 KB |
04.txt | AC | 170 ms | 39168 KB |
05.txt | AC | 260 ms | 99712 KB |
06.txt | AC | 254 ms | 130048 KB |
07.txt | AC | 243 ms | 131840 KB |
08.txt | AC | 239 ms | 132224 KB |
09.txt | AC | 237 ms | 132480 KB |
10.txt | AC | 227 ms | 132048 KB |
11.txt | AC | 129 ms | 12416 KB |
12.txt | AC | 129 ms | 17536 KB |
13.txt | AC | 137 ms | 23424 KB |
14.txt | AC | 265 ms | 123904 KB |
15.txt | AC | 255 ms | 132352 KB |
16.txt | AC | 234 ms | 132048 KB |
17.txt | AC | 229 ms | 132124 KB |
18.txt | AC | 1685 ms | 1408 KB |
19.txt | AC | 1687 ms | 1408 KB |
20.txt | AC | 1867 ms | 1664 KB |
21.txt | AC | 1865 ms | 1664 KB |
22.txt | AC | 1887 ms | 1664 KB |
23.txt | AC | 151 ms | 24448 KB |
24.txt | AC | 140 ms | 12544 KB |
25.txt | AC | 130 ms | 17664 KB |
26.txt | AC | 1589 ms | 1408 KB |
27.txt | AC | 107 ms | 14080 KB |
28.txt | AC | 108 ms | 19456 KB |
29.txt | AC | 100 ms | 18816 KB |
30.txt | AC | 139 ms | 30592 KB |
31.txt | AC | 125 ms | 41088 KB |
32.txt | AC | 112 ms | 28032 KB |
33.txt | AC | 124 ms | 46848 KB |
34.txt | AC | 118 ms | 40320 KB |
35.txt | AC | 134 ms | 53504 KB |
36.txt | AC | 187 ms | 45056 KB |
37.txt | AC | 160 ms | 66452 KB |
38.txt | AC | 159 ms | 66452 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 |