fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef pair<int, int> pii;
  6. typedef pair<ll, ll> pll;
  7.  
  8. #define FOR(i, x, y) for (int i = x, _y = y; i <= _y; ++i)
  9. #define FOD(i, x, y) for (int i = x, _y = y; i >= _y; --i)
  10. #define em emplace
  11. #define emb emplace_back
  12. #define fi first
  13. #define se second
  14.  
  15. template<typename T1, typename T2> bool Tmax (T1 &a, const T2 &b) {if (a < b) {a = b;return true;} return false;}
  16. template<typename T1, typename T2> bool Tmin (T1 &a, const T2 &b) {if (a > b) {a = b;return true;} return false;}
  17.  
  18. void File () {
  19.     #define NAME "TEST"
  20.     if (fopen(NAME".inp", "r")) {
  21.         freopen(NAME".inp", "r", stdin);
  22.         freopen(NAME".out", "w", stdout);
  23.     }    
  24.     else {
  25.         #undef NAME 
  26.         #define NAME "D:\\CPP\\AIO\\Test"
  27.         if (fopen(NAME".inp", "r")) {
  28.             freopen(NAME".inp", "r", stdin);
  29.             freopen(NAME".out", "w", stdout);
  30.         }    
  31.     }
  32. }
  33.  
  34. const char el = '\n';
  35. const int MAXN = 1e6 + 7;
  36. const int INF = 1e9;
  37. const long long MOD = 1e9 + 7;
  38. const long long oo = 1e18;
  39.  
  40. struct Trie {
  41.     struct Node {
  42.         int c[2];
  43.         int cnt, exist;
  44.         Node (): cnt(0), exist(0) { memset(c, -1, sizeof c); }
  45.     };
  46.     vector<Node> nodes;
  47.  
  48.     int cur;
  49.     Trie(): cur(0) {
  50.         nodes.emb(Node());
  51.     }
  52.  
  53.     ll ans = 0;
  54.  
  55.     int new_node() {
  56.         nodes.emb(Node());
  57.         return ++cur;
  58.     }
  59.  
  60.     void add (string x) {
  61.         int pos = 0;
  62.         for (char f : x) {
  63.             int c = f - '0';
  64.             if (nodes[pos].c[c] == -1) {
  65.                 int T = new_node();
  66.                 nodes[pos].c[c] = T;
  67.             }
  68.             pos = nodes[pos].c[c];
  69.             ++nodes[pos].cnt;
  70.         }
  71.         ++nodes[pos].exist;
  72.     }
  73.  
  74.     int get (string x) {
  75.         int pos = 0;
  76.         int temp = 0;
  77.         for (char f : x) {
  78.             int c = f - '0';
  79.             if (nodes[pos].c[c] == -1) {
  80.                 return temp;
  81.             }
  82.             pos = nodes[pos].c[c];
  83.             temp += nodes[pos].exist;
  84.         }
  85.         return nodes[pos].cnt + temp - nodes[pos].exist;
  86.     }
  87. } Tri;
  88.  
  89. int M, N;
  90.  
  91. signed main () {
  92.     ios_base::sync_with_stdio(NULL);
  93.     cin.tie(NULL); cout.tie(NULL);
  94.  
  95.     File();
  96.  
  97.     cin >> M >> N;
  98.  
  99.     FOR(i, 1, M) {
  100.         string S = "";
  101.         int sz; cin >> sz;
  102.         FOR(j, 1, sz) {
  103.             char x; cin >> x;
  104.             S += x;
  105.         }
  106.         Tri.add(S);
  107.     }
  108.  
  109.     FOR(i, 1, N) {
  110.         string S = "";
  111.         int sz; cin >> sz;
  112.         FOR(j, 1, sz) {
  113.             char x; cin >> x;
  114.             S += x;
  115.         }
  116.         cout << Tri.get(S) << el;
  117.     }
  118.  
  119.     return 0;
  120. }
  121.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/RDWsiR
language:
C++14 (gcc 8.3)
created:
8 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!