Submission #660587

#	Time	Username	Problem	Language	Result	Execution time	Memory
660587		HuyKoCoNy	Klasika (COCI20_klasika)	C++17	0 / 110	9 ms	14420 KiB

klasika

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
using namespace std;
// __builtin_popcount
// __builtin_ctz
// #define int long long
#define pii pair<int, int>
#define duoble long double
#define endl '\n'
#define fi first
#define se second
#define mapa make_pair
#define pushb push_back
#define pushf push_front
#define popb pop_back
#define popf pop_front
#define o_ ordered_
#define ins insert
#define era erase
#define pqueue priority_queue
#define minele min_element
#define maxele max_element
#define lb lower_bound // >=
#define ub upper_bound // >
#define debug cout << "NO ERROR", exit(0)
#define FAST ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(v) v.begin(), v.end()
#define SZ(v) (int)v.size()
#define sqr(x) ((x) * (x))

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        if (x > y) {
            x = y;
            return true;
        }
        return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        }
        return false;
    }

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());

int Rand(const int &l, const int &r) {
    assert(l <= r);
    int sz = (r - l + 1);
    return l + rd() % sz;
}


const int MOD = 1e9 + 7; //998244353;
const int LOG = 30;
const int INF = 1e9 + 7;
const int d4x[4] = {-1, 1, 0, 0};
const int d4y[4] = {0, 0, 1, -1};
const char c4[4] = {'U', 'D', 'R', 'L'};
const int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};




// #define LENGTH 1000005
// #define NMOD 2
// #define BASE 256
// const int HashMod[] = {(int)1e9 + 7, (int)1e9 + 2277, (int)1e9 + 5277, (int)1e9 + 8277, (int)1e9 + 9277};

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define o_set tree<int, null_type,less<int>, rb_tree_tag, tree_order_statistics_node_update>
// *(s.find_by_order(2)) : 3rd element in the set i.e. 6
// s.order_of_key(25) : Count of elements strictly smaller than 25 is 4




/* Listen music of IU before enjoy my code */

const int LimN = 2e5 + 5;
int sta[LimN], fin[LimN], timeDFS, NumNode = 1, q, sxor[LimN], ans[LimN];
vector<pii> adj[LimN];

struct Trie {
    Trie* next[2];
    multiset<int> s;
    Trie() {
        for (int i = 0; i < 2; i++) next[i] = NULL;
    }
} TrieRoot;

void insert(const int &state, const int &x) {
    Trie* par = &TrieRoot;
    for (int i = LOG; i >= 0; i--) {
        int c = BIT(state, i);
        if (!par->next[c]) {
            par->next[c] = new Trie();
        }
        // cout << i << " " << c << " " << x << endl;
        par = par->next[c];
        par->s.ins(x);
    }
    // cout << endl;
}


int get(const int &state, const int &sta, const int &fin) {
    Trie *par = &TrieRoot;

    auto ok = [&](Trie *node, int sta, int fin) {
        auto it = node->s.lb(sta);
        if (it != node->s.end() && *it <= fin) return true;
        return false;
    };

    int ans = 0;
    for (int i = LOG; i >= 0; i--) {
        int c = BIT(state, i) ^ 1;
        if (par->next[c] && ok(par->next[c], sta, fin)) {
            par = par->next[c];
            ans |= MASK(i);
        }
        else par = par->next[c ^ 1];
    }
    // debug;
    return ans;
}

struct DataQuery {
    string type;
    int u, v, w;
    void input() {
        cin >> type;
        if (type == "Add") {
            cin >> u >> w;
            NumNode++;
            adj[u].pushb(pii(NumNode, w));
            // cout << u << " " << NumNode << " " << w << endl;
        }
        else {
            cin >> u >> v;
        }
    }
} query[LimN];
 
void dfs(int u) {
    sta[u] = ++timeDFS;
    for (auto [v, w] : adj[u]) {
        sxor[v] = sxor[u] ^ w;
        dfs(v);
    }
    fin[u] = timeDFS;
}



void solve() {

    cin >> q;
    for (int i = 1; i <= q; i++) {
        query[i].input();
    }

    dfs(1);
    NumNode = 1;
    for (int i = 1; i <= q; i++) {
        if (query[i].type == "Add") {
            NumNode++;
            insert(sxor[NumNode], sta[NumNode]);
            // debug;
        }
        else {
            int u = query[i].u;
            int v = query[i].v;
            cout << get(sxor[u], sta[v], fin[v]) << endl;
            // debug;
        }
    }

    


}


/* Authors: Nguyen Minh Huy from Le Quy Don high school for Gifted Students Da Nang */



signed main() {

    #ifndef ONLINE_JUDGE
    freopen("ab.inp", "r", stdin);
    freopen("ab.out", "w", stdout);
    #else
    // freopen("task.inp", "r", stdin);
    // freopen("task.out", "w", stdout);
    #endif
    FAST;
    bool TestCase = 0;
    int NumTest = 1;
    //cin >> NumTest;
    for (int i = 1; i <= NumTest; i++) {
        if (TestCase) cout << "Case" << " " << i << ": ";
        solve();
    }

}

Compilation message (stderr)

klasika.cpp: In function 'int main()':
klasika.cpp:202:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  202 |     freopen("ab.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:203:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  203 |     freopen("ab.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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