oj.uz

Submission #846015

# Submission time Handle Problem Language Result Execution time Memory
846015 2023-09-07T06:09:27 Z efedmrlr Klasika (COCI20_klasika) C++17
33 / 110
 2113 ms 441828 KB 
#include <bits/stdc++.h>

#define int long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int (i) = 0; (i) < (n); (i)++)

using namespace std;

struct TrieNode {
    TrieNode *c[2];
    set<int> st;

    TrieNode() {
        st.clear();
        c[0] = NULL;
        c[1] = NULL;
    }
    bool checkRange(int l, int r) {
        auto lb = st.lower_bound(l), ub = st.upper_bound(r);
        if(ub == st.begin()) return 0;
        if(lb == st.end()) return 0;
        if(ub == st.end() && st.size() < 1) return 0;
        ub--;
        if((*lb) >= l && (*ub) <= r) {
            //cout<<"l:"<<l<<" r:"<<r<<"\n";
            return 1;
        }
        return 0;
    }

    void insert(int num, int disc, int index) {
        st.insert(disc);
        if(index == -1) return;
        bool f = (1 << index) & num;
        if(c[f] == NULL) {
            c[f] = new TrieNode();
        }
        c[f]->insert(num, disc, index-1);

    }
    int query(int num, int l, int r, int index) {
        if(!checkRange(l,r)) {
            return -1;
        } 
        if(index == -1) return 0;
        bool f = (1 << index) & num;
        if(c[f] != NULL) {
            int res = c[f]->query(num,l,r, index-1);
            
            if(res != -1) {
                //cout<<((1 << index) & num) + res<<"\n"; 
                return ((1 << index) & num) + res; 
            }

        }
        if(c[!f] == NULL) {
            return -1;
        };
        int res = ((num ^ INT_MAX) & (1 << index) ) + c[!f]->query(num, l, r, index-1);
        //cout<<res<<"\n";
        return res;
    }


};

const double EPS = 0.00001;
const int INF = 1e9+500;
const int N = 2e5+5;
const int MX = 31;

int n,m,q;
vector<array<int,3> > quer;
int timer = 0;
vector<int> tout(N),tin(N);
vector<vector<int> > adj(N);
vector<int> w(N,0), pathw(N,0);

void dfs(int node, int par) {
    tin[node] = timer++;
    pathw[node] = pathw[par] ^ w[node];
    //cout<<"pathw[par]:"<<pathw[par]<<" w[node]:"<<w[node]<<" path[node]:"<< pathw[node]<<"\n";
    for(auto c : adj[node]) {
        if(c == par) continue;
        dfs(c, node);
    }
    tout[node] = timer++;
}

void solve() {
    cin>>q;
    quer.resize(q);
    int cnt = 2;
    for(int i = 0; i<q; i++) {
        string op;
        cin>>op;
        int a,b;
        if(op == "Query") {
            cin>>a>>b;
            quer[i] = {0, a, b};

        }
        else if(op == "Add") {
            cin>>a>>b;
            adj[cnt].pb(a);
            adj[a].pb(cnt);
            //cout<<b<<"?\n";
            w[cnt] = b;
            quer[i] = {1, a, cnt};
            cnt++;
            
        }   
    }
    dfs(1,0);
    TrieNode *root = new TrieNode();
    int ans = 0;
    root->insert(0, tin[1], MX-1);
    
    
    for(int i = 0; i<q; i++) {
        //cout<<"patlamadı:"<<i<<"\n";
        auto cur = quer[i];
        if(cur[0]) {
            root->insert(pathw[cur[2]], tin[cur[2]], MX-1);
        }
        else {
            int x = pathw[cur[1]];
            x = x ^ INT_MAX;
            int tmp = root->query(x, tin[cur[2]], tout[cur[2]], MX-1);
            ans = tmp ^ pathw[cur[1]];
            cout<<ans<<"\n";
        }
    }
    

}
 
signed main() {
    int test = 1;
    //cin>>test;
    while(test--) {
        solve();
    }
    
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11352 KB Output is correct
2 Correct 5 ms 11608 KB Output is correct
3 Correct 4 ms 11608 KB Output is correct
4 Correct 5 ms 11864 KB Output is correct
5 Incorrect 4 ms 11352 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11352 KB Output is correct
2 Correct 5 ms 11608 KB Output is correct
3 Correct 4 ms 11608 KB Output is correct
4 Correct 5 ms 11864 KB Output is correct
5 Incorrect 4 ms 11352 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 907 ms 130012 KB Output is correct
2 Correct 1265 ms 236732 KB Output is correct
3 Correct 1693 ms 338996 KB Output is correct
4 Correct 1843 ms 441828 KB Output is correct
5 Correct 765 ms 128592 KB Output is correct
6 Correct 1194 ms 234152 KB Output is correct
7 Correct 1653 ms 335116 KB Output is correct
8 Correct 2113 ms 436092 KB Output is correct
9 Correct 770 ms 128252 KB Output is correct
10 Correct 1291 ms 234392 KB Output is correct
11 Correct 1702 ms 336788 KB Output is correct
12 Correct 2061 ms 437500 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11352 KB Output is correct
2 Correct 5 ms 11608 KB Output is correct
3 Correct 4 ms 11608 KB Output is correct
4 Correct 5 ms 11864 KB Output is correct
5 Incorrect 4 ms 11352 KB Output isn't correct
6 Halted 0 ms 0 KB -