oj.uz

Submission #845899

# Submission time Handle Problem Language Result Execution time Memory
845899 2023-09-06T18:27:08 Z vjudge1 Klasika (COCI20_klasika) C++17
33 / 110
 2023 ms 445416 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;
        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 11356 KB Output is correct
2 Correct 4 ms 11612 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 13 ms 22876 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 11356 KB Output is correct
2 Correct 4 ms 11612 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 13 ms 22876 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 790 ms 132764 KB Output is correct
2 Correct 1205 ms 239732 KB Output is correct
3 Correct 1513 ms 342284 KB Output is correct
4 Correct 1779 ms 445416 KB Output is correct
5 Correct 703 ms 131388 KB Output is correct
6 Correct 1202 ms 237344 KB Output is correct
7 Correct 1598 ms 338432 KB Output is correct
8 Correct 2023 ms 440064 KB Output is correct
9 Correct 721 ms 130928 KB Output is correct
10 Correct 1115 ms 237760 KB Output is correct
11 Correct 1521 ms 340592 KB Output is correct
12 Correct 1895 ms 441156 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11356 KB Output is correct
2 Correct 4 ms 11612 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 13 ms 22876 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -