fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct TrieNode {
  5.     int count;
  6.     int children[26];
  7.     int num_children;
  8.     TrieNode() : count(0), num_children(0) {
  9.         for (int i = 0; i < 26; i++) children[i] = -1;
  10.     }
  11. };
  12.  
  13. class Trie {
  14. public:
  15.     vector<TrieNode> trie;
  16.  
  17.     Trie() {
  18.         trie.emplace_back(); 
  19.     }
  20.  
  21.     void insert(const string& s) {
  22.         int node = 0;
  23.         for (char c : s) {
  24.             int idx = c - 'a';
  25.             if (trie[node].children[idx] == -1) {
  26.                 trie[node].children[idx] = trie.size();
  27.                 trie.emplace_back();
  28.             }
  29.             int child = trie[node].children[idx];
  30.             if (trie[child].count == 0) {
  31.                 trie[node].num_children += 1;
  32.             }
  33.             trie[child].count += 1;
  34.             node = child;
  35.         }
  36.     }
  37.  
  38.     void remove_string(const string& s) {
  39.         int node = 0;
  40.         for (char c : s) {
  41.             int idx = c - 'a';
  42.             int child = trie[node].children[idx];
  43.             trie[child].count -= 1;
  44.             if (trie[child].count == 0) {
  45.                 trie[node].num_children -= 1;
  46.             }
  47.             node = child;
  48.         }
  49.     }
  50.  
  51.     int compute_key_presses(const string& s) {
  52.         int key_presses = 0;
  53.         int pos = 0;
  54.         int node = 0;
  55.         while (pos < s.size()) {
  56.             int run = 0;
  57.             int current_node = node;
  58.             while (pos + run < s.size()) {
  59.                 if (trie[current_node].num_children != 1) {
  60.                     break;
  61.                 }
  62.                 char c = s[pos + run];
  63.                 int idx = c - 'a';
  64.                 if (trie[current_node].children[idx] == -1 || trie[trie[current_node].children[idx]].count == 0) {
  65.                     break;
  66.                 }
  67.                 run += 1;
  68.                 current_node = trie[current_node].children[idx];
  69.             }
  70.             if (run > 0) {
  71.                 key_presses += 1;
  72.                 pos += run;
  73.                 node = current_node;
  74.             }
  75.             else {
  76.                 key_presses += 1;
  77.                 char c = s[pos];
  78.                 int idx = c - 'a';
  79.                 int child = trie[node].children[idx];
  80.                 node = child;
  81.                 pos += 1;
  82.             }
  83.         }
  84.         return key_presses;
  85.     }
  86. };
  87.  
  88. int main() {
  89.     ios::sync_with_stdio(false);
  90.     cin.tie(NULL);
  91.     int q;
  92.     cin >> q;
  93.     Trie trie;
  94.     vector<string> file_strings(1); 
  95.     for (int i = 0; i < q; i++) {
  96.         char type;
  97.         cin >> type;
  98.         if (type == '+') {
  99.             string s;
  100.             cin >> s;
  101.             file_strings.push_back(s);
  102.             trie.insert(s);
  103.         }
  104.         else if (type == '-') {
  105.             int a_i;
  106.             cin >> a_i;
  107.             string s = file_strings[a_i];
  108.             trie.remove_string(s);
  109.         }
  110.         else if (type == '?') {
  111.             int a_i;
  112.             cin >> a_i;
  113.             string s = file_strings[a_i];
  114.             int res = trie.compute_key_presses(s);
  115.             cout << res << "\n";
  116.         }
  117.     }
  118. }
Success #stdin #stdout 0s 5260KB
comments (?)
stdin
copy 
9
+ passwords
+ paroli
? 1
? 2
- 1
? 2
+ parol
? 2
? 3
stdout
copy 
3
3
1
1
1
https://ideone.com/qOaZPF
problem BIT2, based on SPOJ submission 11034498 (C++ 4.3.2), 2014-02-09 15:54:15
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!