oj.uz

Submission #845900

# Submission time Handle Problem Language Result Execution time Memory
845900 2023-09-06T18:29:09 Z efedmrlr Klasika (COCI20_klasika) C++17
33 / 110
 2045 ms 441940 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 4 ms 11552 KB Output is correct
2 Correct 6 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 Runtime error 11 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 4 ms 11552 KB Output is correct
2 Correct 6 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 Runtime error 11 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 828 ms 130024 KB Output is correct
2 Correct 1223 ms 236736 KB Output is correct
3 Correct 1527 ms 339236 KB Output is correct
4 Correct 1785 ms 441940 KB Output is correct
5 Correct 695 ms 128592 KB Output is correct
6 Correct 1205 ms 233928 KB Output is correct
7 Correct 1598 ms 335056 KB Output is correct
8 Correct 2045 ms 436140 KB Output is correct
9 Correct 718 ms 128332 KB Output is correct
10 Correct 1119 ms 234680 KB Output is correct
11 Correct 1535 ms 337224 KB Output is correct
12 Correct 1831 ms 437544 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11552 KB Output is correct
2 Correct 6 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 Runtime error 11 ms 22872 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -