oj.uz

Submission #844778

# Submission time Handle Problem Language Result Execution time Memory
844778 2023-09-05T22:38:59 Z vjudge1 Klasika (COCI20_klasika) C++14
33 / 110
 850 ms 524288 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];
    vector<int> ans;
    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;
    push(1, 1, cik[1], gir[1], 0);
    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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7000 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7612 KB Output is correct
4 Correct 4 ms 7772 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 2 ms 7772 KB Output is correct
9 Correct 2 ms 7004 KB Output is correct
10 Correct 2 ms 7260 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 3 ms 7772 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7000 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7612 KB Output is correct
4 Correct 4 ms 7772 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 2 ms 7772 KB Output is correct
9 Correct 2 ms 7004 KB Output is correct
10 Correct 2 ms 7260 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 3 ms 7772 KB Output is correct
13 Correct 9 ms 10076 KB Output is correct
14 Correct 12 ms 13972 KB Output is correct
15 Correct 15 ms 18264 KB Output is correct
16 Correct 19 ms 22016 KB Output is correct
17 Correct 8 ms 10076 KB Output is correct
18 Correct 12 ms 13932 KB Output is correct
19 Correct 15 ms 18012 KB Output is correct
20 Correct 18 ms 21852 KB Output is correct
21 Correct 8 ms 10072 KB Output is correct
22 Correct 12 ms 14012 KB Output is correct
23 Correct 16 ms 18008 KB Output is correct
24 Correct 18 ms 21852 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 850 ms 498796 KB Output is correct
2 Runtime error 720 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7000 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7612 KB Output is correct
4 Correct 4 ms 7772 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 2 ms 7772 KB Output is correct
9 Correct 2 ms 7004 KB Output is correct
10 Correct 2 ms 7260 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 3 ms 7772 KB Output is correct
13 Correct 9 ms 10076 KB Output is correct
14 Correct 12 ms 13972 KB Output is correct
15 Correct 15 ms 18264 KB Output is correct
16 Correct 19 ms 22016 KB Output is correct
17 Correct 8 ms 10076 KB Output is correct
18 Correct 12 ms 13932 KB Output is correct
19 Correct 15 ms 18012 KB Output is correct
20 Correct 18 ms 21852 KB Output is correct
21 Correct 8 ms 10072 KB Output is correct
22 Correct 12 ms 14012 KB Output is correct
23 Correct 16 ms 18008 KB Output is correct
24 Correct 18 ms 21852 KB Output is correct
25 Correct 850 ms 498796 KB Output is correct
26 Runtime error 720 ms 524288 KB Execution killed with signal 9
27 Halted 0 ms 0 KB -