oj.uz

Submission #888099

# Submission time Handle Problem Language Result Execution time Memory
888099 2023-12-16T03:06:46 Z Ahmed_Solyman Klasika (COCI20_klasika) C++14
33 / 110
 1384 ms 524288 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=2e5+5;
set<int>s[30*N];
int id=1,mark=1,l[2*N],r[2*N],trie[30*N][2];
vector<int>adj[2*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 69 ms 341584 KB Output is correct
2 Correct 61 ms 341828 KB Output is correct
3 Correct 67 ms 342532 KB Output is correct
4 Correct 60 ms 341840 KB Output is correct
5 Correct 60 ms 341792 KB Output is correct
6 Correct 61 ms 341840 KB Output is correct
7 Correct 61 ms 341852 KB Output is correct
8 Correct 62 ms 341868 KB Output is correct
9 Correct 62 ms 341588 KB Output is correct
10 Correct 62 ms 341720 KB Output is correct
11 Correct 60 ms 341844 KB Output is correct
12 Correct 61 ms 341964 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 341584 KB Output is correct
2 Correct 61 ms 341828 KB Output is correct
3 Correct 67 ms 342532 KB Output is correct
4 Correct 60 ms 341840 KB Output is correct
5 Correct 60 ms 341792 KB Output is correct
6 Correct 61 ms 341840 KB Output is correct
7 Correct 61 ms 341852 KB Output is correct
8 Correct 62 ms 341868 KB Output is correct
9 Correct 62 ms 341588 KB Output is correct
10 Correct 62 ms 341720 KB Output is correct
11 Correct 60 ms 341844 KB Output is correct
12 Correct 61 ms 341964 KB Output is correct
13 Correct 63 ms 342172 KB Output is correct
14 Correct 66 ms 343164 KB Output is correct
15 Correct 64 ms 343612 KB Output is correct
16 Correct 65 ms 343988 KB Output is correct
17 Correct 62 ms 342204 KB Output is correct
18 Correct 64 ms 342868 KB Output is correct
19 Correct 67 ms 343344 KB Output is correct
20 Correct 65 ms 343892 KB Output is correct
21 Correct 62 ms 342356 KB Output is correct
22 Correct 63 ms 342864 KB Output is correct
23 Correct 64 ms 343376 KB Output is correct
24 Correct 65 ms 343892 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 585 ms 405744 KB Output is correct
2 Correct 997 ms 465536 KB Output is correct
3 Correct 1384 ms 523452 KB Output is correct
4 Runtime error 984 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 341584 KB Output is correct
2 Correct 61 ms 341828 KB Output is correct
3 Correct 67 ms 342532 KB Output is correct
4 Correct 60 ms 341840 KB Output is correct
5 Correct 60 ms 341792 KB Output is correct
6 Correct 61 ms 341840 KB Output is correct
7 Correct 61 ms 341852 KB Output is correct
8 Correct 62 ms 341868 KB Output is correct
9 Correct 62 ms 341588 KB Output is correct
10 Correct 62 ms 341720 KB Output is correct
11 Correct 60 ms 341844 KB Output is correct
12 Correct 61 ms 341964 KB Output is correct
13 Correct 63 ms 342172 KB Output is correct
14 Correct 66 ms 343164 KB Output is correct
15 Correct 64 ms 343612 KB Output is correct
16 Correct 65 ms 343988 KB Output is correct
17 Correct 62 ms 342204 KB Output is correct
18 Correct 64 ms 342868 KB Output is correct
19 Correct 67 ms 343344 KB Output is correct
20 Correct 65 ms 343892 KB Output is correct
21 Correct 62 ms 342356 KB Output is correct
22 Correct 63 ms 342864 KB Output is correct
23 Correct 64 ms 343376 KB Output is correct
24 Correct 65 ms 343892 KB Output is correct
25 Correct 585 ms 405744 KB Output is correct
26 Correct 997 ms 465536 KB Output is correct
27 Correct 1384 ms 523452 KB Output is correct
28 Runtime error 984 ms 524288 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -