Advertisement
Guest User

Untitled

a guest
Oct 25th, 2014
135
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.82 KB | None | 0 0
  1. #pragma comment(linker, "/STACK:256000000")
  2.  
  3. #include <iostream>
  4. #include <cstdio>
  5. #include <algorithm>
  6. #include <cmath>
  7. #include <string>
  8. #include <vector>
  9. #include <functional>
  10. #include <cstring>
  11. #include <set>
  12. #include <map>
  13. #include <ctime>
  14. #include <cassert>
  15.  
  16. using namespace std;
  17.  
  18. #ifdef HOME
  19. const int N = 300;
  20. const int M = 3000;
  21. #else
  22. const int N = 300010;
  23. const int M = 20000000;
  24. #endif
  25.  
  26. void myassert(bool x)
  27. {
  28. #ifdef HOME
  29.     assert(x);
  30. #else
  31.     if (!x)
  32.         exit(0);
  33. #endif
  34. }
  35.  
  36. int mrand()
  37. {
  38.     return rand() ^ (rand() << 12);
  39. }
  40.  
  41. struct Node
  42. {
  43.     Node() : y(mrand()), l(0), r(0) {}
  44.    
  45.     int KEY;
  46.     int VALUE;
  47.     int y;
  48.     int l, r;
  49. };
  50.  
  51. map<string, int> hsh;
  52. vector<string> str;
  53. string _s, _key, _value;
  54. Node node[M];
  55. int nxt_node;
  56. int root[N];
  57.  
  58. int get_copy(int i)
  59. {
  60.     ++nxt_node;
  61.     myassert(nxt_node < M);
  62.     node[nxt_node].l = node[i].l;
  63.     node[nxt_node].r = node[i].r;
  64.     node[nxt_node].KEY = node[i].KEY;
  65.     node[nxt_node].VALUE = node[i].VALUE;
  66.     node[nxt_node].y = node[i].y;
  67.     return nxt_node;
  68. }
  69.  
  70. int calc_hsh(const string& s)
  71. {
  72.     auto it = hsh.find(s);
  73.     if (it != hsh.end())
  74.         return it->second;
  75.     int ret = str.size();
  76.     str.push_back(s);
  77.     hsh[s] = ret;
  78.     return ret;
  79. }
  80.  
  81. int get_hsh(const string& s)
  82. {
  83.     auto it = hsh.find(s);
  84.     if (it != hsh.end())
  85.         return it->second;
  86.     else
  87.         return -1;
  88. }
  89.  
  90. pair<int, int> read()
  91. {
  92.     getline(cin, _s);
  93.     int j = _s.find('=');
  94.     _key = _s.substr(0, j);
  95.     _value = _s.substr(j + 1);
  96.     return make_pair(calc_hsh(_key), calc_hsh(_value));
  97. }
  98.  
  99. int merge(int l, int r)
  100. {
  101.     if (!l || !r)
  102.         return l ? l : r;
  103.     int i;
  104.     if (node[l].y > node[r].y) {
  105.         i = get_copy(l);
  106.         node[i].r = merge(node[l].r, r);
  107.     } else {
  108.         i = get_copy(r);
  109.         node[i].l = merge(l, node[r].l);
  110.     }
  111.     return i;
  112. }
  113.  
  114. int mutable_merge(int l, int r)
  115. {
  116.     if (!l || !r)
  117.         return l ? l : r;
  118.     int i;
  119.     if (node[l].y > node[r].y) {
  120.         i = l;
  121.         node[i].r = mutable_merge(node[l].r, r);
  122.     }
  123.     else {
  124.         i = r;
  125.         node[i].l = mutable_merge(l, node[r].l);
  126.     }
  127.     return i;
  128. }
  129.  
  130. void mutable_split(int t, int k, int& l, int& r)
  131. {
  132.     if (t == 0) {
  133.         l = r = 0;
  134.         return;
  135.     }
  136.     if (node[t].KEY <= k) {
  137.         l = t;
  138.         mutable_split(node[t].r, k, node[l].r, r);
  139.     }
  140.     else {
  141.         r = t;
  142.         mutable_split(node[t].l, k, l, node[r].l);
  143.     }
  144. }
  145.  
  146. void split(int t, int k, int& l, int& r)
  147. {
  148.     if (t == 0) {
  149.         l = r = 0;
  150.         return;
  151.     }
  152.     if (node[t].KEY <= k) {
  153.         l = get_copy(t);
  154.         split(node[t].r, k, node[l].r, r);
  155.     } else {
  156.         r = get_copy(t);
  157.         split(node[t].l, k, l, node[r].l);
  158.     }
  159. }
  160.  
  161. int insert(int t, int KEY, int VALUE)
  162. {
  163.     int fl, fr;
  164.     split(t, KEY, fl, fr);
  165.     int sl, sr;
  166.     split(fl, KEY - 1, sl, sr);
  167.  
  168.     int i = ++nxt_node;
  169.     myassert(nxt_node < M);
  170.     node[i].KEY = KEY;
  171.     node[i].VALUE = VALUE;
  172.     node[i].l = node[i].r = 0;
  173.  
  174.     return merge(merge(sl, i), fr);
  175. }
  176.  
  177. int get_value(int& t, int KEY)
  178. {
  179.     int fl, fr;
  180.     mutable_split(t, KEY, fl, fr);
  181.     int sl, sr;
  182.     mutable_split(fl, KEY - 1, sl, sr);
  183.     int ret = -1;
  184.     if (sr)
  185.         ret = node[sr].VALUE;
  186.     fl = mutable_merge(sl, sr);
  187.     t = mutable_merge(fl, fr);
  188.     return ret;
  189. }
  190.  
  191. void print(const string& s)
  192. {
  193.     cout << s << endl;
  194. }
  195.  
  196. int main()
  197. {
  198. #ifdef HOME
  199.     freopen("input.txt", "r", stdin);
  200.     freopen("output.txt", "w", stdout);
  201. #endif
  202.     str.reserve(N);
  203.     cerr << "sz: " << sizeof(node) << endl;
  204.     int n;
  205.     scanf("%d", &n);
  206.     for (int i = 1; i <= n; ++i)
  207.     {
  208.         int parent, k;
  209.         scanf("%d %d\n", &parent, &k);
  210.         root[i] = root[parent];
  211.         for (int j = 0; j < k; ++j)
  212.         {
  213.             pair<int, int> prt = read();
  214.             root[i] = insert(root[i], prt.first, prt.second);
  215.         }
  216.     }
  217.     int q;
  218.     scanf("%d", &q);
  219.     while (q--)
  220.     {
  221.         int u;
  222.         string KEY;
  223.         cin >> u >> KEY;
  224.         int k = get_hsh(KEY);
  225.         if (k == -1) {
  226.             print("N/A");
  227.             continue;
  228.         }
  229.         int v = get_value(root[u], k);
  230.         if (v == -1) {
  231.             print("N/A");
  232.             continue;
  233.         }
  234.         print(str[v]);
  235.     }
  236.     return 0;
  237. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement