oj.uz

Submission #844770

# Submission time Handle Problem Language Result Execution time Memory
844770 2023-09-05T21:57:40 Z vjudge1 Klasika (COCI20_klasika) C++14
0 / 110
 852 ms 500636 KB 
// Aber der schlimmste Fiend, dem du begegnen kannst, wirst du immer dir selber sein
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ff first
#define ss second
#define pb push_back
#define rev reverse
#define all(x) x.begin(),x.end()
#define acc accumulate
#define sz size()
#define MOD 1000000007
#define rall(x) x.rbegin(),x.rend()
#define rep(i, x, n) for(int i = x; i < n; i++)
using namespace std;
const int N = 2e5 + 5;
struct node{
    node *L = NULL, *R = NULL;
};
struct trie{
    node root;
    void insert(node *cur, int len, int x){
        if(len == -1) return;
        int bit = (x >> len) & 1;
        if(bit && cur->L == NULL){
            cur->L = new node;
        }
        if(!bit && cur->R == NULL){
            cur->R = new node;
        }
        if(bit){
            insert(cur->L, len-1, x);
        }
        else{
            insert(cur->R, len-1, x);
        }
    }
    int find(node *cur, int len, int x){
        if(len == -1){
            return 0;
        }
        int bit = (x >> len) & 1;
        if(bit && cur->R != NULL){
            return find(cur->R, len-1, x) + (1 << len);
        }
        if(!bit && cur->L != NULL){
            return find(cur->L, len-1, x) + (1 << len);
        }
        return find(((cur->L == NULL) ? cur->R : cur->L), len-1, x);
    }
};
vector<pair<int, int> > adj[N];
int gir[N], cik[N], ti = 1;
void dfs(int node, int parent){
    gir[node] = ti++;
    for(int i = 0; i < adj[node].sz; i++){
        if(adj[node][i].ff != parent){
            dfs(adj[node][i].ff, node);
        }
    }
    cik[node] = ti-1;
}
trie seg[4*N];
void push(int i, int l, int r, int p, int x){
    if(l > p || r < p){
        return;
    }
    if(l == r){
        seg[i].insert(&seg[i].root, 30, x);
        return;
    }
    int m = (l + r) / 2;
    push(i*2, l, m, p, x);
    push(i*2+1, m+1, r, p, x);
    seg[i].insert(&seg[i].root, 30, x);
}
int find_range(int i, int l, int r, int ql, int qr, int x){
    if(l > qr || r < ql){
        return 0;
    }
    if(l >= ql && r <= qr){
        if(seg[i].root.L != NULL || seg[i].root.R != NULL){
            return seg[i].find(&seg[i].root, 30, x);
        }
        return 0;
    }
    int m = (l + r) / 2;
    return max(find_range(i*2, l, m, ql, qr, x), find_range(i*2+1, m+1, r, ql, qr, x));
}
inline void solve(){
    int n;
    cin >> n;
    pair<string, pair<int, int> > a[n];
    for(int i = 0; i < n; i++){
        cin >> a[i].ff >> a[i].ss.ff >> a[i].ss.ss;
    }
    int node_count = 1;
    for(int i = 0; i < n; i++){
        if(a[i].ff == "Add"){
            node_count++;
            adj[a[i].ss.ff].pb({node_count, a[i].ss.ss});
            adj[node_count].pb({a[i].ss.ff, a[i].ss.ff});
        }
    }
    dfs(1, 1);
    //for(int i = 1; i <= node_count; i++){
        //cout << gir[i] << " " << cik[i] << endl;
    //}
    int xor_value[node_count+1];
    xor_value[1] = 0;
    node_count = 1;
    for(int i = 0; i < n; i++){
        if(a[i].ff == "Add"){
            node_count++;
            xor_value[node_count] = xor_value[a[i].ss.ff] ^ a[i].ss.ss;
            push(1, 1, cik[1], gir[node_count], xor_value[node_count]);
        }
        else{
            cout << find_range(1, 1, cik[1], gir[a[i].ss.ss], cik[a[i].ss.ss], xor_value[a[i].ss.ff]) << endl;
        }
    }
    //for(int i = 1; i <= node_count; i++){
        //cout << xor_value[i] << " "; 
    //}
}
int main(){
    fast_io
    int t;
    t = 1;
    while(t--) solve();
}

Compilation message

klasika.cpp: In function 'void dfs(int, int)':
klasika.cpp:58:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int i = 0; i < adj[node].sz; i++){
      |                      ^

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Incorrect 2 ms 7260 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Incorrect 2 ms 7260 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 852 ms 500636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Incorrect 2 ms 7260 KB Output isn't correct
3 Halted 0 ms 0 KB -