oj.uz

Submission #336416

# Submission time Handle Problem Language Result Execution time Memory
336416 2020-12-15T09:16:30 Z AriaH Klasika (COCI20_klasika) C++11
110 / 110
 3182 ms 429432 KB 
/// well Fuck this problem Fuck this shitty problem if you are reading my code, dont solve this stupied problem!
/** I can do this all day **/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

#define ll int
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 int LOG = 30;

string ver[N];

int n = 1, ptr = 0, Cnt = 1, q, a[N], b[N], w[N], St[N], Fi[N], child[M][2];

vector < int > G[N];

set < int > st[M];

void dfs(int v)
{
    St[v] = ++ptr;
    for(auto u : G[v])
    {
        dfs(u);
    }
    Fi[v] = ptr;
}
inline void add_trie(int x, int y)
{
    int node = 1;
    for(int T = 30; T >= 0; T--)
    {
        int rem = ((x & (1 << T)) > 0);
        if (child[node][rem] == 0) { child[node][rem] = ++ Cnt; }
        node = child[node][rem];
        st[node].insert(y);
    }
}
inline int ask_trie(int x, int B)
{
    int tl = St[B], tr = Fi[B], node = 1, tot = 0;
    for(int T = 30; T >= 0; T--)
    {
        int rem = ((x & (1 << T)) > 0), 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 = tot + (1 << T); node = other; }
	else { node = child[node][rem]; }
    }
    return tot;
}

int main(){
    fast_io;
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        cin >> ver[i];
        if(ver[i] == "Add") { cin >> a[i] >> b[i]; n ++; w[n] = w[a[i]] ^ b[i]; G[a[i]].push_back(n); a[i] = n; }
	else { cin >> a[i] >> b[i]; }
    }
    dfs(1); add_trie(0, St[1]);
    /// for(int i = 1; i <= n; i ++) cout << St[i] << " " << Fi[i] << endl;
    for (int i = 1; i <= q; i++)
    {
        if(ver[i] == "Add") { add_trie(w[a[i]], St[a[i]]); }
	else { cout << ask_trie(w[a[i]], b[i]) << endl;}
    }
}
/*!
        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 
*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 161772 KB Output is correct
2 Correct 108 ms 161772 KB Output is correct
3 Correct 100 ms 161772 KB Output is correct
4 Correct 100 ms 161900 KB Output is correct
5 Correct 100 ms 161772 KB Output is correct
6 Correct 115 ms 161772 KB Output is correct
7 Correct 101 ms 161772 KB Output is correct
8 Correct 113 ms 161900 KB Output is correct
9 Correct 98 ms 161772 KB Output is correct
10 Correct 99 ms 161900 KB Output is correct
11 Correct 100 ms 161900 KB Output is correct
12 Correct 100 ms 161900 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 161772 KB Output is correct
2 Correct 108 ms 161772 KB Output is correct
3 Correct 100 ms 161772 KB Output is correct
4 Correct 100 ms 161900 KB Output is correct
5 Correct 100 ms 161772 KB Output is correct
6 Correct 115 ms 161772 KB Output is correct
7 Correct 101 ms 161772 KB Output is correct
8 Correct 113 ms 161900 KB Output is correct
9 Correct 98 ms 161772 KB Output is correct
10 Correct 99 ms 161900 KB Output is correct
11 Correct 100 ms 161900 KB Output is correct
12 Correct 100 ms 161900 KB Output is correct
13 Correct 102 ms 162560 KB Output is correct
14 Correct 106 ms 163052 KB Output is correct
15 Correct 105 ms 163692 KB Output is correct
16 Correct 106 ms 164332 KB Output is correct
17 Correct 103 ms 162412 KB Output is correct
18 Correct 116 ms 163080 KB Output is correct
19 Correct 106 ms 163692 KB Output is correct
20 Correct 106 ms 164332 KB Output is correct
21 Correct 109 ms 162284 KB Output is correct
22 Correct 114 ms 163052 KB Output is correct
23 Correct 107 ms 163692 KB Output is correct
24 Correct 106 ms 164332 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 937 ms 230892 KB Output is correct
2 Correct 1586 ms 299500 KB Output is correct
3 Correct 2184 ms 363912 KB Output is correct
4 Correct 2901 ms 429172 KB Output is correct
5 Correct 993 ms 232184 KB Output is correct
6 Correct 1661 ms 296332 KB Output is correct
7 Correct 2357 ms 359012 KB Output is correct
8 Correct 2992 ms 422208 KB Output is correct
9 Correct 944 ms 231916 KB Output is correct
10 Correct 1598 ms 296940 KB Output is correct
11 Correct 2257 ms 360812 KB Output is correct
12 Correct 2873 ms 423984 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 161772 KB Output is correct
2 Correct 108 ms 161772 KB Output is correct
3 Correct 100 ms 161772 KB Output is correct
4 Correct 100 ms 161900 KB Output is correct
5 Correct 100 ms 161772 KB Output is correct
6 Correct 115 ms 161772 KB Output is correct
7 Correct 101 ms 161772 KB Output is correct
8 Correct 113 ms 161900 KB Output is correct
9 Correct 98 ms 161772 KB Output is correct
10 Correct 99 ms 161900 KB Output is correct
11 Correct 100 ms 161900 KB Output is correct
12 Correct 100 ms 161900 KB Output is correct
13 Correct 102 ms 162560 KB Output is correct
14 Correct 106 ms 163052 KB Output is correct
15 Correct 105 ms 163692 KB Output is correct
16 Correct 106 ms 164332 KB Output is correct
17 Correct 103 ms 162412 KB Output is correct
18 Correct 116 ms 163080 KB Output is correct
19 Correct 106 ms 163692 KB Output is correct
20 Correct 106 ms 164332 KB Output is correct
21 Correct 109 ms 162284 KB Output is correct
22 Correct 114 ms 163052 KB Output is correct
23 Correct 107 ms 163692 KB Output is correct
24 Correct 106 ms 164332 KB Output is correct
25 Correct 937 ms 230892 KB Output is correct
26 Correct 1586 ms 299500 KB Output is correct
27 Correct 2184 ms 363912 KB Output is correct
28 Correct 2901 ms 429172 KB Output is correct
29 Correct 993 ms 232184 KB Output is correct
30 Correct 1661 ms 296332 KB Output is correct
31 Correct 2357 ms 359012 KB Output is correct
32 Correct 2992 ms 422208 KB Output is correct
33 Correct 944 ms 231916 KB Output is correct
34 Correct 1598 ms 296940 KB Output is correct
35 Correct 2257 ms 360812 KB Output is correct
36 Correct 2873 ms 423984 KB Output is correct
37 Correct 1543 ms 234756 KB Output is correct
38 Correct 2112 ms 299628 KB Output is correct
39 Correct 2640 ms 365584 KB Output is correct
40 Correct 3021 ms 429432 KB Output is correct
41 Correct 1734 ms 232428 KB Output is correct
42 Correct 2309 ms 296192 KB Output is correct
43 Correct 2770 ms 358892 KB Output is correct
44 Correct 3182 ms 421740 KB Output is correct
45 Correct 1736 ms 232428 KB Output is correct
46 Correct 2347 ms 297224 KB Output is correct
47 Correct 2823 ms 359788 KB Output is correct
48 Correct 3154 ms 423992 KB Output is correct