Submission #1306510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306510		dzhoz0	Klasika (COCI20_klasika)	C++20	33 / 110	766 ms	547552 KiB

klasika

/*
    it could have been better :)
    it will next time ;)
*/
#include <bits/stdc++.h>
using namespace std;

#define INF 1e18
#define f first
#define s second
#define pii pair<int, int>
#define vi vector<int>

const int MOD = 1'000'000'000 + 7;

void setIO(string name = "")
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
#ifdef LOCAL
    freopen("inp.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#else
    if (!name.empty())
    {
        freopen((name + ".INP").c_str(), "r", stdin);
        freopen((name + ".OUT").c_str(), "w", stdout);
    }
#endif
}

struct Trie {
    struct Node {
        int cnt = 0;
        int child[2] = {-1, -1};
    };

    vector<Node> trie = {Node()};

    void add(int x) {
        int node = 0;
        for(int b = 30; b >= 0; b--) {
            int cur = (x >> b) & 1;
            if(trie[node].child[cur] == -1) {
                trie[node].child[cur] = trie.size();
                trie.emplace_back();
            }
            node = trie[node].child[cur]; 
        }
        trie[node].cnt++;
    }

    int query(int x) {
        int node = 0;
        int cur_value = 0;
        for(int b = 30; b >= 0; b--) {
            int cur = 1 - ((x >> b) & 1); 
            if(trie[node].child[cur] != -1) node = trie[node].child[cur];
            else if(trie[node].child[1 - cur] != -1) { 
                node = trie[node].child[1 - cur];
                cur = 1 - cur;
            }
            else return x;
            if(cur == 1) cur_value |= (1 << b);
        }
        if(trie[node].cnt > 0) return cur_value;
        return x;
    }
};

struct Query {
    int type;
    int x, y, w;
};

const int MAXN = 2e5;
Trie st[4 * MAXN + 5];
int d[MAXN + 5];
vi g[MAXN + 5];
int tin[MAXN + 5], tout[MAXN + 5];

void upd(int id, int l, int r, int k, int x) {
    if(k < l || r < k) return;    
    st[id].add(x);
    if(l == r) return;
    int mid = (l + r) / 2;
    upd(id * 2, l, mid, k, x);
    upd(id * 2 + 1, mid + 1, r, k, x);
}

int query(int id, int l, int r, int u, int v, int x) {
    if(v < l || r < u) return 0;
    if(u <= l && r <= v) return st[id].query(x) ^ x;
    int mid = (l + r) / 2;
    return max(query(id * 2, l, mid, u, v, x), query(id * 2 + 1, mid + 1, r, u, v, x));
}

int timeDfs = 0;
void dfs(int u) {
    tin[u] = ++timeDfs;
    for(int &v : g[u]) dfs(v);
    tout[u] = timeDfs;
}

void solve()
{
    int q; cin >> q;
    vector<Query> queries(q);
    {
        int cur = 1; 
        for(auto &it : queries) {
            string s; cin >> s;
            if(s == "Add") it.type = 0;
            else it.type = 1;
            cin >> it.x;
            if(it.type == 0) {
                cin >> it.w;
                it.y = ++cur;
                g[it.x].push_back(it.y);
            }
            else {
                cin >> it.y;
            }
            // cout << it.x << ' ' << it.y << ' ' << it.w << '\n';

        }
    }

    dfs(1);
    upd(1, 1, MAXN, tin[1], 0);

    // for(int i =1 ; i <= 3; i++) cout << tin[i] << ' ' << tout[i] << '\n'; 
    for(auto &it : queries) {
        if(it.type == 0) {
            d[it.y] = d[it.x] ^ it.w;
            // cout << d[it.x] << ' ' << it.w << '\n';
            upd(1, 1, MAXN, tin[it.y], d[it.y]);
        }
        else {
            cout << query(1, 1, MAXN, tin[it.y], tout[it.y], d[it.x]) << '\n';
        }
    }
    // for(int i = 1; i <= 3; i++) cout << d[i] << '\n';
}
signed main()
{
    setIO();
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}

Compilation message (stderr)

klasika.cpp: In function 'void setIO(std::string)':
klasika.cpp:26:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         freopen((name + ".INP").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:27:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         freopen((name + ".OUT").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 0 / 33
• Subtask 4: 0 / 44