oj.uz

Submission #888101

# Submission time Handle Problem Language Result Execution time Memory
888101 2023-12-16T03:22:58 Z Ahmed_Solyman Klasika (COCI20_klasika) C++14
110 / 110
 2261 ms 419560 KB 
/*
In the name of Allah
made by: Ahmed_Solyman
*/
#include <bits/stdc++.h>
#include <ext/rope>
 
using namespace std;
using namespace __gnu_cxx;
#pragma GCC optimize("-Ofast")
#pragma GCC optimize("-O1")
//-------------------------------------------------------------//
typedef long long ll;
typedef unsigned long long ull;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define PI acos(-1)
#define lb lower_bound
#define ub upper_bound
#define endl '\n'
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define sum_to(n) (n*(n+1))/2
#define pb push_back
#define pf push_front
#define fil(arr,x) memset(arr,x,sizeof(arr))
const ll mod=1e9+7;
int dx[8]={0,1,0,-1,1,1,-1,-1};
int dy[8]={1,0,-1,0,1,-1,-1,1};
//-------------------------------------------------------------//
ll lcm(ll a,ll b)
{
    return (max(a,b)/__gcd(a,b))*min(a,b);
}
void person_bool(bool x)
{
    cout<<(x?"YES":"NO")<<endl;
}
const int N=3e5+5;
set<int>s[10*N];
int id=1,mark=1,l[N],r[N],trie[10*N][2];
vector<int>adj[N];
void insert(int x,int ind){
    int p=0;
    for(int i=29;i>=0;i--){
        bool g=x & (1<<i);
        if(~trie[p][g])p=trie[p][g];
        else p=trie[p][g]=id++;
        s[p].insert(ind);
    }
}
int solve(int a,int b){
    int p=0,ret=0;
    for(int i=29;i>=0;i--){
        bool g=a & (1<<i);g^=1;
        if(~trie[p][g] && s[trie[p][g]].lower_bound(l[b])!=s[trie[p][g]].end() && *s[trie[p][g]].lower_bound(l[b])<=r[b])p=trie[p][g],ret|=(1<<i);
        else p=trie[p][g^1];
    }
    return ret;
}
void dfs(int node,int p){
    l[node]=mark++;
    for(auto i:adj[node])
        if(i!=p)
            dfs(i,node);
    r[node]=mark-1;
}
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    #ifndef ONLINE_JUDGE
 //   freopen("input.in", "r", stdin);
   // freopen("output.out", "w", stdout);
    #endif
    fast
    fil(trie,-1);
    int q;cin>>q;
    vector<int>d(q+1);
    int v=2;
    vector<array<int,3>>e;
    while(q--){
        string s;cin>>s;
        if(s=="Add"){
            int u,w;cin>>u>>w;
            d[v]=d[u]^w;
            e.push_back({0,u,v});
            adj[u].push_back(v++);
        }
        else{
            int a,b;cin>>a>>b;
            e.push_back({1,a,b});
        }
    }
    dfs(1,1);
    insert(0,l[1]);
    for(auto i:e){
        int t=i[0],u=i[1],v=i[2];
        if(t==0){
            insert(d[v],l[v]);
        }
        else{
            cout<<solve(d[u],v)<<endl;
        }
    }
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 174068 KB Output is correct
2 Correct 33 ms 174172 KB Output is correct
3 Correct 32 ms 174188 KB Output is correct
4 Correct 32 ms 174428 KB Output is correct
5 Correct 32 ms 174164 KB Output is correct
6 Correct 33 ms 174160 KB Output is correct
7 Correct 32 ms 174172 KB Output is correct
8 Correct 33 ms 174424 KB Output is correct
9 Correct 33 ms 174172 KB Output is correct
10 Correct 32 ms 174164 KB Output is correct
11 Correct 33 ms 174168 KB Output is correct
12 Correct 33 ms 174420 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 174068 KB Output is correct
2 Correct 33 ms 174172 KB Output is correct
3 Correct 32 ms 174188 KB Output is correct
4 Correct 32 ms 174428 KB Output is correct
5 Correct 32 ms 174164 KB Output is correct
6 Correct 33 ms 174160 KB Output is correct
7 Correct 32 ms 174172 KB Output is correct
8 Correct 33 ms 174424 KB Output is correct
9 Correct 33 ms 174172 KB Output is correct
10 Correct 32 ms 174164 KB Output is correct
11 Correct 33 ms 174168 KB Output is correct
12 Correct 33 ms 174420 KB Output is correct
13 Correct 35 ms 174672 KB Output is correct
14 Correct 36 ms 175452 KB Output is correct
15 Correct 37 ms 176112 KB Output is correct
16 Correct 37 ms 176468 KB Output is correct
17 Correct 35 ms 174680 KB Output is correct
18 Correct 35 ms 175196 KB Output is correct
19 Correct 37 ms 175960 KB Output is correct
20 Correct 37 ms 176476 KB Output is correct
21 Correct 34 ms 174676 KB Output is correct
22 Correct 36 ms 175196 KB Output is correct
23 Correct 36 ms 176152 KB Output is correct
24 Correct 42 ms 176516 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 587 ms 238116 KB Output is correct
2 Correct 1046 ms 298144 KB Output is correct
3 Correct 1383 ms 355912 KB Output is correct
4 Correct 1838 ms 418476 KB Output is correct
5 Correct 603 ms 238536 KB Output is correct
6 Correct 1095 ms 295820 KB Output is correct
7 Correct 1540 ms 352004 KB Output is correct
8 Correct 2044 ms 408836 KB Output is correct
9 Correct 576 ms 239172 KB Output is correct
10 Correct 1041 ms 297548 KB Output is correct
11 Correct 1437 ms 354928 KB Output is correct
12 Correct 1794 ms 411140 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 174068 KB Output is correct
2 Correct 33 ms 174172 KB Output is correct
3 Correct 32 ms 174188 KB Output is correct
4 Correct 32 ms 174428 KB Output is correct
5 Correct 32 ms 174164 KB Output is correct
6 Correct 33 ms 174160 KB Output is correct
7 Correct 32 ms 174172 KB Output is correct
8 Correct 33 ms 174424 KB Output is correct
9 Correct 33 ms 174172 KB Output is correct
10 Correct 32 ms 174164 KB Output is correct
11 Correct 33 ms 174168 KB Output is correct
12 Correct 33 ms 174420 KB Output is correct
13 Correct 35 ms 174672 KB Output is correct
14 Correct 36 ms 175452 KB Output is correct
15 Correct 37 ms 176112 KB Output is correct
16 Correct 37 ms 176468 KB Output is correct
17 Correct 35 ms 174680 KB Output is correct
18 Correct 35 ms 175196 KB Output is correct
19 Correct 37 ms 175960 KB Output is correct
20 Correct 37 ms 176476 KB Output is correct
21 Correct 34 ms 174676 KB Output is correct
22 Correct 36 ms 175196 KB Output is correct
23 Correct 36 ms 176152 KB Output is correct
24 Correct 42 ms 176516 KB Output is correct
25 Correct 587 ms 238116 KB Output is correct
26 Correct 1046 ms 298144 KB Output is correct
27 Correct 1383 ms 355912 KB Output is correct
28 Correct 1838 ms 418476 KB Output is correct
29 Correct 603 ms 238536 KB Output is correct
30 Correct 1095 ms 295820 KB Output is correct
31 Correct 1540 ms 352004 KB Output is correct
32 Correct 2044 ms 408836 KB Output is correct
33 Correct 576 ms 239172 KB Output is correct
34 Correct 1041 ms 297548 KB Output is correct
35 Correct 1437 ms 354928 KB Output is correct
36 Correct 1794 ms 411140 KB Output is correct
37 Correct 1020 ms 242324 KB Output is correct
38 Correct 1487 ms 300952 KB Output is correct
39 Correct 1772 ms 360968 KB Output is correct
40 Correct 2065 ms 419560 KB Output is correct
41 Correct 1120 ms 239096 KB Output is correct
42 Correct 1570 ms 296436 KB Output is correct
43 Correct 1964 ms 352732 KB Output is correct
44 Correct 2261 ms 409336 KB Output is correct
45 Correct 1105 ms 239336 KB Output is correct
46 Correct 1589 ms 297204 KB Output is correct
47 Correct 1933 ms 353852 KB Output is correct
48 Correct 2100 ms 411672 KB Output is correct