#include <bits/stdc++.h>
using namespace std;
// Templates here
template<typename T1, typename T2, typename T3>
class triple {
public:
T1 first;
T2 second;
T3 third;
triple() {
first = 0;
second = 0;
third = 0;
}
};
// Typedefs here
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef set<int> si;
typedef set<ll> sl;
typedef set<pii> spii;
typedef set<pll> spll;
typedef map<string, int> mpsi;
typedef map<string, ll> mpsl;
typedef map<int, int> mpii;
typedef map<ll, ll> mpll;
// Defines here
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define fora(i, a, b) for(int (i)=(a);(i)<(b);(i)++)
#define forla(i, a, b) for(ll (i)=(a);(i)<(b);(i)++)
#define for0(i, b) fora((i),0,(b))
#define forl0(i, b) forla((i),0,(b))
#define rofa(i, a, b) for(int (i)=(a);(i)>=(b);(i)--)
#define rofla(i, a, b) for(ll (i)=(a);(i)>=(b);(i)--)
#define rof0(i, a) rofa((i),(a),0)
#define rofl0(i, a) rofla((i),(a),0)
#define forag(i, a, b, g) for(int (i)=(a);(i)<(b);(i)+=(g))
#define forlag(i, a, b, g) for(ll (i)=(a);(i)<(b);(i)+=(g))
#define for0g(i, b, g) forag((i),0,(b),(g))
#define forl0g(i, b, g) forlag((i),0,(b),(g))
#define rofag(i, a, b, g) for(int (i)=(a);(i)>=(b);(i)-=(g))
#define roflag(i, a, b, g) for(ll (i)=(a);(i)>=(b);(i)-=(g))
#define rof0g(i, a, g) rofag((i),(a),0,(g))
#define rofl0g(i, a, g) roflag((i),(a),0,(g))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define pf push_front
#define MP make_pair
#define F first
#define S second
#define GraphM1(g, n) int (g)[(n)][(n)]
#define GraphM2(g, n) vi (g)[(n)]
// Const variables here
const int maxn = 2e5 + 5;
// Before structs global variables here
// Structs here
struct Node {
Node *child[2];
Node *p = nullptr;
int h, id, cnt;
si s;
Node() {
h = -1;
id = -1;
cnt = 0;
for (auto &i : child)
i = nullptr;
}
};
struct Trie {
Node *root;
int strType, cnt;
Trie() {
strType = '0';
cnt = 1;
root = new Node();
root->h = 0;
root->id = 1;
}
void add(string st, int num) {
Node *cur = root;
cur->cnt++;
cur->s.insert(num);
for (char c:st) {
int x = int(c) - strType;
if (cur->child[x] == nullptr) {
cur->child[x] = new Node();
Node *next = cur->child[x];
next->p = cur;
next->h = cur->h + 1;
next->id = ++cnt;
}
cur = cur->child[x];
cur->cnt++;
cur->s.insert(num);
}
}
};
// Global variables here
int st[maxn], et[maxn], A[maxn];
vpii g[maxn];
vector<pair<int, pii>> query;
int temp;
// Functions here
string Base2(int x) {
string ans;
while (x > 0) {
ans += to_string(x % 2);
x /= 2;
}
return ans;
}
int Base10(string s) {
int ans = 0, po = 1;
rof0(i,(int)s.size()-1) {
ans += (s[i] == '0') * po;
po *= 2;
}
return ans;
}
void dfs(int x) {
st[x] = temp++;
for0(i, (int) g[x].size()) {
A[g[x][i].F] = (A[x] ^ g[x][i].S);
dfs(g[x][i].F);
}
et[x] = temp++;
}
string find(int x, int y, Node *root) {
string mab = Base2(A[x]);
string ans;
Node *cur = root;
for (char c:mab) {
int temp1 = c - '0';
int temp2 = (temp1 ^ 1);
if (cur->child[temp2] and !cur->child[temp2]->s.empty()) {
auto it = cur->child[temp2]->s.lower_bound(st[y]);
if (it != cur->child[temp2]->s.end() and *it <= et[y]) {
cur = cur->child[temp2];
ans += '1';
continue;
}
}
cur = cur->child[temp1];
ans += '0';
}
return ans;
}
// Main here
int main() {
IOS
int n;
cin >> n;
int id = 1;
for0(i, n) {
string s;
int a, b;
cin >> s >> a >> b;
if (s == "Add") {
g[a].pb(MP(++id, b));
query.pb(MP(0, MP(id, 0)));
} else
query.pb(MP(1, MP(a, b)));
}
dfs(1);
Trie *T = new Trie();
T->add(Base2(A[1]), st[1]);
for0(q, n) {
int qt = query[q].F;
if (qt == 1) {
int x = query[q].S.F;
T->add(Base2(A[x]), st[x]);
} else {
int x = query[q].S.F, b = query[q].S.S;
string ret = find(x, b, T->root);
cout << Base10(ret) << "\n";
}
}
return 0;
}
Compilation message
klasika.cpp: In function 'int Base10(std::string)':
klasika.cpp:44:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
44 | #define rofa(i, a, b) for(int (i)=(a);(i)>=(b);(i)--)
| ^
klasika.cpp:46:20: note: in expansion of macro 'rofa'
46 | #define rof0(i, a) rofa((i),(a),0)
| ^~~~
klasika.cpp:147:5: note: in expansion of macro 'rof0'
147 | rof0(i,(int)s.size()-1) {
| ^~~~
klasika.cpp: In function 'void dfs(int)':
klasika.cpp:40:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
40 | #define fora(i, a, b) for(int (i)=(a);(i)<(b);(i)++)
| ^
klasika.cpp:42:20: note: in expansion of macro 'fora'
42 | #define for0(i, b) fora((i),0,(b))
| ^~~~
klasika.cpp:158:5: note: in expansion of macro 'for0'
158 | for0(i, (int) g[x].size()) {
| ^~~~
klasika.cpp: In function 'int main()':
klasika.cpp:40:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
40 | #define fora(i, a, b) for(int (i)=(a);(i)<(b);(i)++)
| ^
klasika.cpp:42:20: note: in expansion of macro 'fora'
42 | #define for0(i, b) fora((i),0,(b))
| ^~~~
klasika.cpp:202:5: note: in expansion of macro 'for0'
202 | for0(i, n) {
| ^~~~
klasika.cpp:40:31: warning: unnecessary parentheses in declaration of 'q' [-Wparentheses]
40 | #define fora(i, a, b) for(int (i)=(a);(i)<(b);(i)++)
| ^
klasika.cpp:42:20: note: in expansion of macro 'fora'
42 | #define for0(i, b) fora((i),0,(b))
| ^~~~
klasika.cpp:219:5: note: in expansion of macro 'for0'
219 | for0(q, n) {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
9932 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
9932 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
85 ms |
24084 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
9932 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
