oj.uz

Submission #846029

# Submission time Handle Problem Language Result Execution time Memory
846029 2023-09-07T07:06:25 Z vjudge1 Klasika (COCI20_klasika) C++17
0 / 110
 671 ms 136980 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MAXN = 2e5;

#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
    #define OPEN freopen(".in", "r", stdin); \
                 freopen(".out", "w", stdout);
#else
    #define OPEN void(23);
#endif

vector <pair <int, int>> adj[MAXN];
int in[MAXN], out[MAXN];

struct Node
{
    set <int> inds;
    Node *l = NULL, *r = NULL;
    Node() {inds.clear();}
};

struct Trie
{
    Node *root;
    Trie() {root = new Node();}

    void add(int x, int ind) {add(x, ind, root);}
    void add(int x, int ind, Node *node, int bit = 32)
    {
        node->inds.emplace(ind);
        if(bit < 0) return;
        if(((x >> bit) & 1))
        {
            if(node->r == NULL) node->r = new Node();
            add(x, ind, node->r, bit -1);
        }
        else
        {
            if(node->l == NULL) node->l = new Node();
            add(x, ind, node->l, bit -1);
        }
    }

    bool check(Node *node, int l, int r)
    {
        return node->inds.lower_bound(l) != node->inds.upper_bound(r);
    }

    int query(int x, int l, int r) {return query(x, l, r, root);}
    int query(int x, int l, int r, Node *node, int bit = 32)
    {
        if(bit < 0) return 0;
        if((x >> bit) & 1)
        {
            if(node->l != NULL && check(node->l, l, r)) return (1 << bit) + query(x, l, r, node->l, bit -1);
            return query(x, l, r, node->r, bit -1);
        }
        else
        {
            if(node->r != NULL && check(node->r, l, r)) return (1 << bit) + query(x, l, r, node->r, bit -1);
            return query(x, l, r, node->l, bit -1);
        }
    }
};

void solve()
{
    int q; cin >> q;
    vector <tuple <string, int, int>> queries(q);
    for(auto &[s, a, b] : queries) cin >> s >> a >> b;

    vector <int> dists(2);
    dists[1] = 0;
    int cnt = 2;
    for(auto &[s, a, b] : queries)
    {
        if(s[0] == 'A')
        {
            adj[a].emplace_back(cnt, b);
            dists.emplace_back(dists[a] ^ b);
            cnt++;
        }
    }

    int timer = 0;
    function <void(int)> dfs = [&](int node) -> void
    {
        in[node] = ++timer;
        for(auto &[child, d] : adj[node])
            dfs(child);

        out[node] = timer;
    };

    dfs(1);

    Trie trie;
    trie.add(0, 0);

    int nw = 2;
    for(auto &[s, a, b] : queries)
    {
        if(s[0] == 'Q')
        {
            cout << trie.query(dists[a], in[b], out[b]) << "\n";
        }
        else
        {
            trie.add(dists[nw], in[nw]);
            nw++;
        }
    }

    return;
}

int32_t main()
{
    OPEN;

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t = 1; //cin >> t;
    while(t--)
    {
        solve();
    }
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8280 KB Output is correct
2 Incorrect 2 ms 8280 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8280 KB Output is correct
2 Incorrect 2 ms 8280 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 671 ms 136980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8280 KB Output is correct
2 Incorrect 2 ms 8280 KB Output isn't correct
3 Halted 0 ms 0 KB -