fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAX_NODES = 2000005;
  5.  
  6. int children[MAX_NODES][26];
  7. int count_nodes[MAX_NODES];
  8. bool is_end_node[MAX_NODES];
  9. int num_children_nodes[MAX_NODES];
  10. int next_node = 1; 
  11.  
  12. void initialize_trie() {
  13.     memset(children[0], -1, sizeof(children[0]));
  14.     count_nodes[0] = 0;
  15.     is_end_node[0] = false;
  16.     num_children_nodes[0] = 0;
  17. }
  18.  
  19. void insert_string(const string& s) {
  20.     int node = 0;
  21.     for (char c : s) {
  22.         int idx = c - 'a';
  23.         if (children[node][idx] == -1) {
  24.             children[node][idx] = next_node;
  25.             memset(children[next_node], -1, sizeof(children[next_node]));
  26.             count_nodes[next_node] = 0;
  27.             is_end_node[next_node] = false;
  28.             num_children_nodes[next_node] = 0;
  29.             next_node++;
  30.             if (next_node >= MAX_NODES) {
  31.                 cerr << "Превышено максимальное количество узлов Trie.\n";
  32.                 exit(1);
  33.             }
  34.         }
  35.         int child = children[node][idx];
  36.         if (count_nodes[child] == 0) {
  37.             num_children_nodes[node] += 1;
  38.         }
  39.         count_nodes[child] += 1;
  40.         node = child;
  41.     }
  42.     is_end_node[node] = true;
  43. }
  44.  
  45. void remove_string_func(const string& s) {
  46.     int node = 0;
  47.     for (char c : s) {
  48.         int idx = c - 'a';
  49.         int child = children[node][idx];
  50.         count_nodes[child] -= 1;
  51.         if (count_nodes[child] == 0) {
  52.             num_children_nodes[node] -= 1;
  53.         }
  54.         node = child;
  55.     }
  56.     is_end_node[node] = false;
  57. }
  58.  
  59. int compute_key_presses_func(const string& s) {
  60.     int key_presses = 0;
  61.     int pos = 0;
  62.     int node = 0;
  63.     int n = s.size();
  64.     while (pos < n) {
  65.         bool is_press_point = (num_children_nodes[node] > 1) || is_end_node[node];
  66.         if (is_press_point) {
  67.             key_presses += 1;
  68.             char c = s[pos];
  69.             int idx = c - 'a';
  70.             if (children[node][idx] == -1 || count_nodes[children[node][idx]] == 0) {
  71.                 break;
  72.             }
  73.             node = children[node][idx];
  74.             pos += 1;
  75.         }
  76.         else {
  77.             int run = 0;
  78.             int current_node = node;
  79.             while (pos + run < n) {
  80.                 bool is_press_point_here = (num_children_nodes[current_node] > 1) || is_end_node[current_node];
  81.                 if (is_press_point_here) {
  82.                     break;
  83.                 }
  84.                 char c = s[pos + run];
  85.                 int idx = c - 'a';
  86.                 if (children[current_node][idx] == -1 || count_nodes[children[current_node][idx]] == 0) {
  87.                     break;
  88.                 }
  89.                 run += 1;
  90.                 current_node = children[current_node][idx];
  91.             }
  92.             if (run > 0) {
  93.                 key_presses += 1;
  94.                 node = current_node;
  95.                 pos += run;
  96.             }
  97.             else {
  98.                 key_presses += 1;
  99.                 char c = s[pos];
  100.                 int idx = c - 'a';
  101.                 if (children[node][idx] == -1 || count_nodes[children[node][idx]] == 0) {
  102.                     break;
  103.                 }
  104.                 node = children[node][idx];
  105.                 pos += 1;
  106.             }
  107.         }
  108.     }
  109.     return key_presses;
  110. }
  111.  
  112. int main() {
  113.     ios::sync_with_stdio(false);
  114.     cin.tie(NULL);
  115.     initialize_trie();
  116.     int q;
  117.     cin >> q;
  118.     vector<string> file_strings(1); 
  119.     for (int i = 0; i < q; i++) {
  120.         char type;
  121.         cin >> type;
  122.         if (type == '+') {
  123.             string s;
  124.             cin >> s;
  125.             file_strings.push_back(s);
  126.             insert_string(s);
  127.         }
  128.         else if (type == '-') {
  129.             int a_i;
  130.             cin >> a_i;
  131.             if (a_i >= 1 && a_i < (int)file_strings.size()) {
  132.                 string s = file_strings[a_i];
  133.                 remove_string_func(s);
  134.             }
  135.         }
  136.         else if (type == '?') {
  137.             int a_i;
  138.             cin >> a_i;
  139.             if (a_i >= 1 && a_i < (int)file_strings.size()) {
  140.                 string s = file_strings[a_i];
  141.                 int res = compute_key_presses_func(s);
  142.                 cout << res << "\n";
  143.             }
  144.         }
  145.     }
  146.     return 0;
  147. }
Success #stdin #stdout 0.01s 9772KB
comments (?)
stdin
copy 
9
+ passwords
+ paroli
? 1
? 2
- 1
? 2
+ parol
? 2
? 3
stdout
copy 
3
3
1
2
1
https://ideone.com/1UmRxV
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!