/******************************
* author : @marvinthang *
* date : 17 / 11 / 2021 *
******************************/
#include <bits/stdc++.h>
using namespace std;
#define superspeed ios_base::sync_with_stdio(false);\
cin.tie(NULL);\
//cout.tie(NULL);
#define file(name) freopen(name".inp", "r", stdin);\
freopen(name".out", "w", stdout);
const int MOD = 1e9 + 7; // 998244353;
const double PI = 3.1415926535897932384626433832795; // acos((db)-1); atan(-1.0);
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
const long long oo = 1e18;
const int MAX = 2e5 + 5;
int Q, N = 1, in[MAX], out[MAX], timeDfs, dist[MAX], A[MAX], B[MAX];
vector <pair <int, int>> adj[MAX];
string type[MAX];
void dfs(int u, int par) {
in[u] = ++timeDfs;
for (auto &x: adj[u]) {
int v = x.second;
int w = x.first;
if (v == par) continue;
dist[v] = dist[u] ^ w;
dfs(v, u);
}
out[u] = timeDfs;
}
struct TrieNode {
TrieNode *child[2];
set <int> s;
TrieNode() {
child[0] = child[1] = nullptr;
s.clear();
}
};
const int LOG = 31;
TrieNode *root = new TrieNode();
void TrieInsert(int val, int pos) {
TrieNode *p = root;
for (int i = LOG - 1; i >= 0; --i) {
int bit = (val >> i) & 1;
if (p -> child[bit] == nullptr) p -> child[bit] = new TrieNode();
p = p -> child[bit];
p -> s.insert(pos);
}
}
int TrieMaxXOR(int val, int l, int r) {
TrieNode *p = root;
int res = 0;
for (int i = LOG - 1; i >= 0; --i) {
int bit = (val >> i) & 1;
if (p -> child[bit ^ 1] != nullptr) {
set <int> :: iterator x = p -> child[bit ^ 1] -> s.lower_bound(l);
if (*x <= r && x != p -> child[bit ^ 1] -> s.end()) {
p = p -> child[bit ^ 1];
res |= (1 << i);
} else p = p -> child[bit];
} else p = p -> child[bit];
}
return res;
}
int main() {
superspeed;
#ifndef ONLINE_JUDGE
file("XORPATH");
#endif
cin >> Q;
for (int i = 1; i <= Q; ++i) {
cin >> type[i] >> A[i] >> B[i];
if (type[i] == "Add") {
int u = A[i];
int v = ++N;
int w = B[i];
A[i] = v;
adj[u].push_back({w, v});
adj[v].push_back({w, u});
}
}
dfs(1, 0);
TrieInsert(dist[1], in[1]);
for (int i = 1; i <= Q; ++i) {
if (type[i] == "Add") {
TrieInsert(dist[A[i]], in[A[i]]);
} else {
cout << TrieMaxXOR(dist[A[i]], in[B[i]], out[B[i]]) << '\n';
}
}
return 0;
}
Compilation message
klasika.cpp: In function 'int main()':
klasika.cpp:13:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
13 | #define file(name) freopen(name".inp", "r", stdin);\
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:79:2: note: in expansion of macro 'file'
79 | file("XORPATH");
| ^~~~
klasika.cpp:14:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
14 | freopen(name".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:79:2: note: in expansion of macro 'file'
79 | file("XORPATH");
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
11348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
11348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
11328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
11348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
