# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
336407 |
2020-12-15T08:35:00 Z |
AriaH |
Klasika (COCI20_klasika) |
C++11 |
|
1215 ms |
219400 KB |
/** I can do this all day **/
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#define Mp make_pair
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define endl "\n"
const ll N = 2e5 + 10;
const ll M = 16 * N;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 30;
ll q, n = 1, ptr, Cnt = 1, w[N], St[N], Fi[N], child[N][2];
set < ll > st[M];
vector < ll > G[N];
pair < string, pll > Q[N];
void dfs(int v)
{
St[v] = ++ptr;
for(auto u : G[v])
{
dfs(u);
}
Fi[v] = ptr;
}
/// add trie -> x = w ash ta root, v = starting time rasi ke mikhai add bokoni
inline void add_trie(ll x, ll y)
{
ll node = 1;
for(int T = 30; ~T; T --)
{
ll rem = (x >> T) % 2;
if(child[node][rem] == 0) /// set nashode
{
child[node][rem] = ++Cnt;
}
node = child[node][rem];
st[node].insert(y);
}
}
/// check v, node -> aya toye set trie v rasi hast ke toye sub node bashe ya na
/*
inline bool check(int v, int node)
{
auto it = st[v].lower_bound(St[node]);
if(it == st[v].end() || *it > Fi[node]) return 0;
return 1;
}
*/
/// ask trie x, b -> maximum xor ke adadmoon = x, va toye sub v bashe
inline ll ask_trie(ll x, ll b)
{
ll tl = St[b], tr = Fi[b];
ll node = 1, tot = 0;
for(ll T = 30; ~T; T --)
{
ll rem = (x >> T) % 2, other = child[node][1 ^ rem], is_Ok = 1;
auto it = st[other].lower_bound(tl);
if(it == st[other].end() || *it > tr) is_Ok = 0;
if(is_Ok)
{
tot += (1ll << T);
node = other;
}
else
{
node = child[node][rem];
}
}
return tot;
}
int main()
{
cin >> q;
for(int i = 1; i <= q; i ++)
{
string s;
ll a, b;
cin >> s >> a >> b;
Q[i] = Mp(s, Mp(a, b));
if(s == "Add")
{
n ++;
w[n] = w[a] ^ b;
G[a].push_back(n);
Q[i].S.F = n;
}
}
dfs(1);
add_trie(0, 1);
for(int i = 1; i <= q; i ++)
{
if(Q[i].F == "Add")
{
add_trie(w[Q[i].S.F], St[Q[i].S.F]);
}
else
{
cout << ask_trie(w[Q[i].S.F], Q[i].S.S) << endl;
}
}
return 0;
}
/*!
stay away from negative people they have a problem for every solution !
*/
/*
4
Add 1 5
Query 1 1
Add 1 7
Query 1 1
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
114 ms |
164972 KB |
Output is correct |
2 |
Correct |
113 ms |
164844 KB |
Output is correct |
3 |
Correct |
122 ms |
164972 KB |
Output is correct |
4 |
Correct |
112 ms |
165100 KB |
Output is correct |
5 |
Correct |
108 ms |
164844 KB |
Output is correct |
6 |
Correct |
108 ms |
165100 KB |
Output is correct |
7 |
Correct |
107 ms |
164972 KB |
Output is correct |
8 |
Correct |
110 ms |
164972 KB |
Output is correct |
9 |
Correct |
110 ms |
164844 KB |
Output is correct |
10 |
Correct |
107 ms |
164844 KB |
Output is correct |
11 |
Correct |
106 ms |
165100 KB |
Output is correct |
12 |
Correct |
107 ms |
164972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
114 ms |
164972 KB |
Output is correct |
2 |
Correct |
113 ms |
164844 KB |
Output is correct |
3 |
Correct |
122 ms |
164972 KB |
Output is correct |
4 |
Correct |
112 ms |
165100 KB |
Output is correct |
5 |
Correct |
108 ms |
164844 KB |
Output is correct |
6 |
Correct |
108 ms |
165100 KB |
Output is correct |
7 |
Correct |
107 ms |
164972 KB |
Output is correct |
8 |
Correct |
110 ms |
164972 KB |
Output is correct |
9 |
Correct |
110 ms |
164844 KB |
Output is correct |
10 |
Correct |
107 ms |
164844 KB |
Output is correct |
11 |
Correct |
106 ms |
165100 KB |
Output is correct |
12 |
Correct |
107 ms |
164972 KB |
Output is correct |
13 |
Correct |
111 ms |
165612 KB |
Output is correct |
14 |
Correct |
120 ms |
166380 KB |
Output is correct |
15 |
Correct |
114 ms |
167148 KB |
Output is correct |
16 |
Correct |
117 ms |
167916 KB |
Output is correct |
17 |
Correct |
112 ms |
165484 KB |
Output is correct |
18 |
Correct |
124 ms |
166252 KB |
Output is correct |
19 |
Correct |
126 ms |
167020 KB |
Output is correct |
20 |
Correct |
116 ms |
167660 KB |
Output is correct |
21 |
Correct |
114 ms |
165484 KB |
Output is correct |
22 |
Correct |
118 ms |
166380 KB |
Output is correct |
23 |
Correct |
123 ms |
166960 KB |
Output is correct |
24 |
Correct |
124 ms |
167660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1215 ms |
219400 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
114 ms |
164972 KB |
Output is correct |
2 |
Correct |
113 ms |
164844 KB |
Output is correct |
3 |
Correct |
122 ms |
164972 KB |
Output is correct |
4 |
Correct |
112 ms |
165100 KB |
Output is correct |
5 |
Correct |
108 ms |
164844 KB |
Output is correct |
6 |
Correct |
108 ms |
165100 KB |
Output is correct |
7 |
Correct |
107 ms |
164972 KB |
Output is correct |
8 |
Correct |
110 ms |
164972 KB |
Output is correct |
9 |
Correct |
110 ms |
164844 KB |
Output is correct |
10 |
Correct |
107 ms |
164844 KB |
Output is correct |
11 |
Correct |
106 ms |
165100 KB |
Output is correct |
12 |
Correct |
107 ms |
164972 KB |
Output is correct |
13 |
Correct |
111 ms |
165612 KB |
Output is correct |
14 |
Correct |
120 ms |
166380 KB |
Output is correct |
15 |
Correct |
114 ms |
167148 KB |
Output is correct |
16 |
Correct |
117 ms |
167916 KB |
Output is correct |
17 |
Correct |
112 ms |
165484 KB |
Output is correct |
18 |
Correct |
124 ms |
166252 KB |
Output is correct |
19 |
Correct |
126 ms |
167020 KB |
Output is correct |
20 |
Correct |
116 ms |
167660 KB |
Output is correct |
21 |
Correct |
114 ms |
165484 KB |
Output is correct |
22 |
Correct |
118 ms |
166380 KB |
Output is correct |
23 |
Correct |
123 ms |
166960 KB |
Output is correct |
24 |
Correct |
124 ms |
167660 KB |
Output is correct |
25 |
Incorrect |
1215 ms |
219400 KB |
Output isn't correct |
26 |
Halted |
0 ms |
0 KB |
- |