oj.uz

Submission #846013

# Submission time Handle Problem Language Result Execution time Memory
846013 2023-09-07T06:04:01 Z efedmrlr Klasika (COCI20_klasika) C++17
33 / 110
 2049 ms 443856 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; 
            }

        }
        assert(c[!f] != NULL);
        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 5 ms 11352 KB Output is correct
2 Correct 4 ms 11608 KB Output is correct
3 Correct 4 ms 11612 KB Output is correct
4 Correct 4 ms 11868 KB Output is correct
5 Runtime error 12 ms 22872 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11352 KB Output is correct
2 Correct 4 ms 11608 KB Output is correct
3 Correct 4 ms 11612 KB Output is correct
4 Correct 4 ms 11868 KB Output is correct
5 Runtime error 12 ms 22872 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 803 ms 131664 KB Output is correct
2 Correct 1195 ms 238648 KB Output is correct
3 Correct 1512 ms 340832 KB Output is correct
4 Correct 1769 ms 443856 KB Output is correct
5 Correct 789 ms 130628 KB Output is correct
6 Correct 1233 ms 235860 KB Output is correct
7 Correct 1642 ms 337200 KB Output is correct
8 Correct 2049 ms 438168 KB Output is correct
9 Correct 716 ms 129848 KB Output is correct
10 Correct 1136 ms 236160 KB Output is correct
11 Correct 1474 ms 338964 KB Output is correct
12 Correct 1827 ms 439716 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11352 KB Output is correct
2 Correct 4 ms 11608 KB Output is correct
3 Correct 4 ms 11612 KB Output is correct
4 Correct 4 ms 11868 KB Output is correct
5 Runtime error 12 ms 22872 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -