Submission #697703

#	Time	Username	Problem	Language	Result	Execution time	Memory
697703		gagik_2007	Klasika (COCI20_klasika)	C++17	110 / 110	2915 ms	523032 KiB

klasika

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <chrono>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <functional>
#include <random>
#include <cassert>
using namespace std;

typedef long long ll;
typedef long double ld;

#define ff first
#define ss second

const ll K = 2;

struct Vertex {
    ll to[K];
    set<ll>inds;
    Vertex() {
        for (ll i = 0; i < K; i++) {
            to[i] = -1;
        }
    }
};

ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll N = 200007;
const ll LG = 30;
ll n, m, k;
vector<Vertex>p(1);
vector<pair<ll, ll>>q;
vector<pair<ll, ll>>g[N];
ll vl[N];
ll ind[N];
ll sz[N];
ll timer = 0;

void dfs(ll v, ll val = 0, ll par = -1) {
    sz[v] = 1;
    ind[v] = timer++;
    if (par != -1) {
        vl[v] = vl[par] ^ val;
    }
    for (ll i = 0; i < g[v].size(); i++) {
        ll to = g[v][i].ff;
        ll w = g[v][i].ss;
        if (to != par) {
            dfs(to, w, v);
            sz[v] += sz[to];
        }
    }
}

void add(ll x, ll i) {
    ll v = 0;
    p[v].inds.insert(i);
    for (ll j = LG; j >= 0; j--) {
        ll c = 0;
        if (x & (1ll << j)) {
            c = 1;
        }
        if (p[v].to[c] == -1) {
            p[v].to[c] = p.size();
            p.emplace_back();
        }
        p[p[v].to[c]].inds.insert(i);
        //cout << v << ": " << p[v].to[0] << " " << p[v].to[1] << endl;
        v = p[v].to[c];
    }
}

ll get_ans(ll x, ll i) {
    ll v = 0;
    ll ans = 0;
    for (ll j = LG; j >= 0; j--) {
        if (x & (1ll << j)) {
            if (p[v].to[0] != -1) {
                auto it = p[p[v].to[0]].inds.lower_bound(ind[i]);
                //cout << res << " 1 ";
                if ((it != p[p[v].to[0]].inds.end()) && (*it < ind[i] + sz[i])) {
                    v = p[v].to[0];
                    ans += (1ll << j);
                }
                else {
                    v = p[v].to[1];
                }
            }
            else {
                v = p[v].to[1];
            }
        }
        else {
            if (p[v].to[1] != -1) {
                auto it = p[p[v].to[1]].inds.lower_bound(ind[i]);
                //cout << res << " 2 ";
                if ((it != p[p[v].to[1]].inds.end()) && (*it < ind[i] + sz[i])) {
                    v = p[v].to[1];
                    ans += (1ll << j);
                }
                else {
                    v = p[v].to[0];
                }
            }
            else {
                v = p[v].to[0];
            }
        }
    }
    //cout << endl;
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    ll cur = 2;
    vl[1] = 0;
    for (ll i = 0; i < n; i++) {
        ll x, y;
        string tp;
        cin >> tp >> x >> y;
        if (tp == "Add") {
            g[x].push_back({ cur,y });
            q.push_back({ -1,cur });
            cur++;
        }
        else {
            q.push_back({ x,y });
        }
    }
    dfs(1);
    /*for (ll i = 1; i <= n; i++) {
        cout << i << ": " << vl[i] << endl;
    }
    cout << endl;*/
    //cout << "HASA STE\n";
    add(vl[1], ind[1]);
    for (ll i = 0; i < n; i++) {
        if (q[i].ff == -1) {
            ll v = q[i].ss;
            //cout << "ADDING: " << v << endl;
            add(vl[v], ind[v]);
        }
        else {
            cout << get_ans(vl[q[i].ff], q[i].ss) << endl;
        }
    }
    return 0;
}

/// ---- - --------  ------ -------- -- - - -
/// Just a reminder. Ubuntu password is I O I
/// ---- - --------  ------ -------- -- - - -

Compilation message (stderr)

klasika.cpp: In function 'void dfs(ll, ll, ll)':
klasika.cpp:61:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for (ll i = 0; i < g[v].size(); i++) {
      |                    ~~^~~~~~~~~~~~~

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