제출 #1293757

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1293757		i_love_kim_ji_won	Klasika (COCI20_klasika)	C++20	110 / 110	1709 ms	432680 KiB

klasika

// I ♡ 김지원
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define freopen(name) if(fopen(name".INP","r")) {freopen (name".INP","r",stdin); freopen (name".OUT","w",stdout);}
using namespace std;

using ll = long long;

void justDoIt();

int main() {
    // freopen("");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    justDoIt();
    return 0;
}

const int N = 2e5 + 5;

const int numnodes = 7e6 + 5;

int st[N], en[N];
vector<int> g[N];
string type[N];
int tin[N], tout[N];
int val[N];

// struct Trie {
//     struct Node {
//         int child[2];
//         set<int> s;
//     } nodes[numnodes];
//     int cur;
//     Trie() : cur(0) {
//         memset(nodes[0].child, -1, sizeof(nodes[0].child));
//         nodes[0].s.clear();
//     };
//     int new_node() {
//         cur++;
//         memset(nodes[cur].child, -1, sizeof(nodes[cur].child));
//         nodes[cur].s.clear();
//         return cur;
//     }
//     void add_num(int x, int t) {
//         int pos = 0;
//         for (int i = 30; i >= 0; i--) {
//             int c = (x >> i & 1);
//             if (nodes[pos].child[c] == -1) {
//                 nodes[pos].child[c] = new_node();
//             }
//             pos = nodes[pos].child[c];
//             nodes[pos].s.insert(t);
//         }
//     }
//     int query(int x, int l, int r) {
//         int res = 0, pos = 0;
//         for (int i = 30; i >= 0; i--) {
//             for (int v = 1; v >= 0; v--) {
//                 int c = (v ^ (x >> i & 1));
//                 if (nodes[pos].child[c] == -1) {continue;}
//                 auto idx = nodes[nodes[pos].child[c]].s.lower_bound(l);
//                 if (idx == nodes[nodes[pos].child[c]].s.end() || *idx > r) {continue;}
//                 pos = nodes[pos].child[c];
//                 res += (v << i);
//                 break;
//             }
//         }
//         return res;
//     }
// } T;

struct Trie {
    struct Node {
        Node* child[2];
        set<int> s;
        Node () {
            child[0] = child[1] = NULL;

        }
    };
    int cur;
    Node* root;
    Trie () : cur(0) {
        root = new Node();
    };
    void add_num(int x, int t) {
        Node* p = root;
        for (int i = 30; i >= 0; i--) {
            int c = (x >> i & 1);
            if (p->child[c] == NULL) {
                p->child[c] = new Node();
            }
            p = p-> child[c];
            p->s.insert(t);
        }
    }
    int query(int x, int l, int r) {
        int res = 0;
        Node* p = root;
        for (int i = 30; i >= 0; i--) {
            int c = (x >> i & 1);
            c ^= 1;
            if (p->child[c] == NULL ||
                p->child[c]->s.lower_bound(l) == p->child[c]->s.upper_bound(r)) {
                p = p->child[c ^ 1];
            }
            else {
                res += (1 << i);
                p = p->child[c];
            }
        }
        return res;
    }
} T;

int timer = 0;
 
void dfs(int u, int p = 0) {
    tin[u] = ++timer;
    for (int v : g[u]) {
        if (v == p) {continue;}
        dfs(v, u);
    }
    tout[u] = timer;
}

void test() {
    int q;
    cin >> q;
    int curr = 1;
    for (int i = 1; i <= q; i++) {
        cin >> type[i] >> st[i] >> en[i];
        if (type[i] == "Add") {
            g[++curr].push_back(st[i]);
            g[st[i]].push_back(curr);
            val[curr] = val[st[i]] ^ en[i];
        }
    }
    dfs(1);
    curr = 1;
    T.add_num(val[1], tin[1]);
    for (int i = 1; i <= q; i++) {
        if (type[i] == "Add") {
            curr++;
            T.add_num(val[curr], tin[curr]);
        }
        else {
            cout << T.query(val[st[i]], tin[en[i]], tout[en[i]]) << '\n';
        }
    }
}

void justDoIt() {
    int t = 1;
    // cin >> t;
    for (int tests = 1; tests <= t; tests++) {
        test();
    }
}

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