Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma comment(linker, "/STACK:256000000")
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cmath>
- #include <string>
- #include <vector>
- #include <functional>
- #include <cstring>
- #include <set>
- #include <map>
- #include <ctime>
- #include <cassert>
- using namespace std;
- #ifdef HOME
- const int N = 300;
- const int M = 3000;
- #else
- const int N = 300010;
- const int M = 20000000;
- #endif
- void myassert(bool x)
- {
- #ifdef HOME
- assert(x);
- #else
- if (!x)
- exit(0);
- #endif
- }
- int mrand()
- {
- return rand() ^ (rand() << 12);
- }
- struct Node
- {
- Node() : y(mrand()), l(0), r(0) {}
- int KEY;
- int VALUE;
- int y;
- int l, r;
- };
- map<string, int> hsh;
- vector<string> str;
- string _s, _key, _value;
- Node node[M];
- int nxt_node;
- int root[N];
- int get_copy(int i)
- {
- ++nxt_node;
- myassert(nxt_node < M);
- node[nxt_node].l = node[i].l;
- node[nxt_node].r = node[i].r;
- node[nxt_node].KEY = node[i].KEY;
- node[nxt_node].VALUE = node[i].VALUE;
- node[nxt_node].y = node[i].y;
- return nxt_node;
- }
- int calc_hsh(const string& s)
- {
- auto it = hsh.find(s);
- if (it != hsh.end())
- return it->second;
- int ret = str.size();
- str.push_back(s);
- hsh[s] = ret;
- return ret;
- }
- int get_hsh(const string& s)
- {
- auto it = hsh.find(s);
- if (it != hsh.end())
- return it->second;
- else
- return -1;
- }
- pair<int, int> read()
- {
- getline(cin, _s);
- int j = _s.find('=');
- _key = _s.substr(0, j);
- _value = _s.substr(j + 1);
- return make_pair(calc_hsh(_key), calc_hsh(_value));
- }
- int merge(int l, int r)
- {
- if (!l || !r)
- return l ? l : r;
- int i;
- if (node[l].y > node[r].y) {
- i = get_copy(l);
- node[i].r = merge(node[l].r, r);
- } else {
- i = get_copy(r);
- node[i].l = merge(l, node[r].l);
- }
- return i;
- }
- int mutable_merge(int l, int r)
- {
- if (!l || !r)
- return l ? l : r;
- int i;
- if (node[l].y > node[r].y) {
- i = l;
- node[i].r = mutable_merge(node[l].r, r);
- }
- else {
- i = r;
- node[i].l = mutable_merge(l, node[r].l);
- }
- return i;
- }
- void mutable_split(int t, int k, int& l, int& r)
- {
- if (t == 0) {
- l = r = 0;
- return;
- }
- if (node[t].KEY <= k) {
- l = t;
- mutable_split(node[t].r, k, node[l].r, r);
- }
- else {
- r = t;
- mutable_split(node[t].l, k, l, node[r].l);
- }
- }
- void split(int t, int k, int& l, int& r)
- {
- if (t == 0) {
- l = r = 0;
- return;
- }
- if (node[t].KEY <= k) {
- l = get_copy(t);
- split(node[t].r, k, node[l].r, r);
- } else {
- r = get_copy(t);
- split(node[t].l, k, l, node[r].l);
- }
- }
- int insert(int t, int KEY, int VALUE)
- {
- int fl, fr;
- split(t, KEY, fl, fr);
- int sl, sr;
- split(fl, KEY - 1, sl, sr);
- int i = ++nxt_node;
- myassert(nxt_node < M);
- node[i].KEY = KEY;
- node[i].VALUE = VALUE;
- node[i].l = node[i].r = 0;
- return merge(merge(sl, i), fr);
- }
- int get_value(int& t, int KEY)
- {
- int fl, fr;
- mutable_split(t, KEY, fl, fr);
- int sl, sr;
- mutable_split(fl, KEY - 1, sl, sr);
- int ret = -1;
- if (sr)
- ret = node[sr].VALUE;
- fl = mutable_merge(sl, sr);
- t = mutable_merge(fl, fr);
- return ret;
- }
- void print(const string& s)
- {
- cout << s << endl;
- }
- int main()
- {
- #ifdef HOME
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- str.reserve(N);
- cerr << "sz: " << sizeof(node) << endl;
- int n;
- scanf("%d", &n);
- for (int i = 1; i <= n; ++i)
- {
- int parent, k;
- scanf("%d %d\n", &parent, &k);
- root[i] = root[parent];
- for (int j = 0; j < k; ++j)
- {
- pair<int, int> prt = read();
- root[i] = insert(root[i], prt.first, prt.second);
- }
- }
- int q;
- scanf("%d", &q);
- while (q--)
- {
- int u;
- string KEY;
- cin >> u >> KEY;
- int k = get_hsh(KEY);
- if (k == -1) {
- print("N/A");
- continue;
- }
- int v = get_value(root[u], k);
- if (v == -1) {
- print("N/A");
- continue;
- }
- print(str[v]);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement