Submission #500972

#	Time	Username	Problem	Language	Result	Execution time	Memory
500972		someone	Klasika (COCI20_klasika)	C++14	110 / 110	666 ms	245768 KiB

klasika

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5 + 42, INF = 1e18 + 42, MOD = 1e9 + 7;

struct Query {
    int a, t;
};

struct Node {
    int id[2], mini;
};

struct Trie {
    int sz = 0;
    vector<Query> q;
    vector<Node> node;

    Trie() {
        node.push_back({{-1, -1}, INF});
    }

    void insert(int val, int t) {
        int a = 0;
        q.push_back({val, t});
        for(int i = 29; i > -1; i--) {
            int b = min((val & (1 << i)), 1ll);
            if(node[a].id[b] == -1) {
                node[a].id[b] = ++sz;
                node.push_back({{-1, -1}, INF});
            }
            a = node[a].id[b];
            node[a].mini = min(node[a].mini, t);
        }
    }

    int getMax(int val, int t) {
        int ans = 0, a = 0;
        for(int i = 29; i > -1; i--) {
            ans <<= 1;
            int b = min((val & (1 << i)), 1ll);
            if(node[a].id[1 - b] != -1 && node[node[a].id[1 - b]].mini < t) {
                ans++;
                a = node[a].id[1 - b];
            } else
                a = node[a].id[b];
        }
        return ans;
    }
};

vector<Query> q[N];
vector<int> adj[N];
int n, XOR[N], temps[N], ans[N];

Trie DFS(int i) {
    Trie act;
    act.insert(XOR[i], temps[i]);
    for(int j : adj[i]) {
        Trie child = DFS(j);
        if(child.q.size() > act.q.size())
            swap(child, act);
        for(Query req : child.q)
            act.insert(req.a, req.t);
    }
    for(Query req : q[i])
        ans[req.t] = act.getMax(XOR[req.a], req.t);
    return act;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    int nb = 1;
    for(int i = 0; i < n; i++)
        ans[i] = -1;
    for(int i = 0; i < n; i++) {
        string str;
        int a, b;
        cin >> str >> a >> b;
        if(str[0] == 'A') {
            a--;
            temps[nb] = i;
            adj[a].push_back(nb);
            XOR[nb] = XOR[a] ^ b;
            nb++;
        } else {
            q[b-1].push_back({a-1, i});
        }
    }

    DFS(0);
    for(int i = 0; i < n; i++)
        if(ans[i] != -1)
            cout << ans[i] << '\n';
}

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