Submission #1114373

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1114373	2024-11-18T17:14:17 Z	tintingyn21	Klasika (COCI20_klasika)	C++17	33 / 110	713 ms	524288 KB

klasika

// author : daohuyenchi



#ifdef LOCAL
    #include "D:\C++ Submit\debug.h"
#else
    #define debug(...)
#endif



#include <bits/stdc++.h>

using namespace std;

#define ull unsigned long long
#define db double
#define i32 int32_t  
#define i64 int64_t 
#define ll long long
// 
#define fi first
#define se second


//                                      #define int long long    // consider carefully


//
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define pil pair<int, ll> 
#define PAIR make_pair 
//                                      TIME IS LIMITED ...  
#define  rep(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define repd(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define repv(v, H) for(auto &v: H)
//                                      REFLECT ON THE PAST ...
#define RESET(c, x) memset(c, x, sizeof(c))
#define MASK(i) (1LL << (i))
#define BIT(mask, i) (((mask) >> (i)) & 1LL)
#define ONBIT(mask, i) ((mask) | (1LL << (i)))
#define OFFBIT(mask, i) ((mask) &~ (1LL << (i)))
#define COUNTBIT __builtin_popcountll
//                                      30 / 1 / 2024 ? love is zero... start from zero 
#define vi vector <int>
#define vll vector <ll>
#define lwb lower_bound
#define upb upper_bound
#define all(v) (v).begin(), (v).end()
#define special(H) (H).resize(distance(H.begin(), unique(all(H))))
//                                      
#define sp ' ' 
#define nl '\n'
#define EL {cerr << '\n';}
#define yes "YES"
#define no "NO"
#define Log2(n) (63 - __builtin_clzll(n))
#define left __left__
#define right __right__ 
#define lps(id) ((id) << 1)
#define rps(id) ((id) << 1 | 1)

//____________________________________________________________________


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

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

template <class... T>
void print(T&&... n) {
    using exp = int[];
    exp{0, (cerr << n << sp, 0)...};
    cerr << nl;
}

template <class T, class... C>
void assign(int n, T v, C&&... a) {
    using e = int[];
    e{(a.assign(n, v), 0)...};
}

template <class... C>
void resize(int n, C&&... a) {
    using e = int[];
    e{(a.resize(n), 0)...};
}

template <class T>
using vector2d = vector<vector<T>>;
template <class T>
using vector3d = vector<vector2d<T>>;

template <class T> int ssize(T &a) { return (int) a.size(); }


//____________________________________________________________________


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

const int MOD      = 1000000007;
// const int MOD[2] = {1000000009, 998244353};

template<class X> void modmize(X &x, int cur_Mod = MOD) {
    if(x >= cur_Mod) x -= cur_Mod;
    if(x < 0) x += cur_Mod;
}

const long long oo = 1e18 + 7;
const long long LINF = 1e18 + 7;
const int IINF      = 2e9;
const int nmax     = 2e5 + 10;
const int MAX      = 2e5;
const int base     = 311;
const db eps       = 1e-6;
const int block    = 500;
static const double PI = acos(-1.0);

//____________________________________________________________________


int n, Q;
vector <pii> G[nmax];

array <int, 3> qs[nmax];

int pf[nmax];
int par[nmax][22], dep[nmax];
int ein[nmax], tour[nmax], eout[nmax];
int timer = 0;
void dfs(int u, int p) {
    par[u][0] = p;
    rep (k, 1, 18) {
        par[u][k] = par[par[u][k - 1]][k - 1];
    }
    dep[u] = dep[p] + 1;
    ein[u] = ++timer;
    tour[timer] = u;
    repv (e, G[u]) {
        int v = e.se;
        int w = e.fi;
        if (v == p) continue;
        pf[v] = pf[u] ^ w;
        dfs(v, u);
    }
    eout[u] = timer;
}

int get_lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int d = dep[u] - dep[v];
    repd (k, 18, 0) if (BIT(d, k) == 1) u = par[u][k];
    if (u == v) return u;
    repd (k, 18, 0) {
        if (par[u][k] != par[v][k]) {
            u = par[u][k];
            v = par[v][k];
        }
    }
    return par[u][0];
}

struct Node {
    int child[2];
    int cnt = 0;
    Node() {
        cnt = 0;
        rep (i, 0, 1) child[i] = -1;
    }
} ;

struct Trie {

    vector <Node> t;
    Trie() {
        assign(1, Node(), t);
        rep (k, 0, 1) {
            // assert(t[0].child[k] == -1);
        }
    }

    int new_node() {
        t.push_back(Node());
        // assert(ssize(t) > 1);
        return ssize(t) - 1;
    }    

    bool check_exist(int cur) {
        return cur != -1 && t[cur].cnt > 0;
    }

    void add(int x) {
        int cur = 0;
        repd (i, 30, 0) {
            int k = BIT(x, i);
            if (t[cur].child[k] == -1) {
                t[cur].child[k] = ssize(t);
                t.push_back(Node());
                // print(t[cur].child[k], ssize(t) - 1);
            }
            // print(i, cur);
            cur = t[cur].child[k];
            t[cur].cnt++;
        }
    }

    void del(int x) {
        int cur = 0;
        repd (i, 30, 0) {
            int k = BIT(x, i);
            cur = t[cur].child[k];
            // assert(cur != -1);
            t[cur].cnt--;
        }
    }

    int get_xor(int x) {
        int cur = 0;
        int ans = 0;
        repd (i, 30, 0) {
            int k = BIT(x, i);
            if (check_exist(t[cur].child[k ^ 1])) {
                ans |= 1 << i;
                cur = t[cur].child[k ^ 1];
            }
            else if (check_exist(t[cur].child[k])) {
                cur = t[cur].child[k];
            }
            else break;
        }
        return ans;
    }

} st[nmax * 4];

vector <int> sav[nmax * 4];

void build(int id, int l, int r) {
    // debug(id, l, r);
    if (l == r) {
        sav[id].push_back(pf[tour[l]]);
    }
    else {
        int mid = (l + r) / 2;
        build(lps(id), l, mid);
        build(rps(id), mid + 1, r);
        merge(sav[lps(id)].begin(), sav[lps(id)].end(), sav[rps(id)].begin(), sav[rps(id)].end(), back_inserter(sav[id]));
    }

    repv (v, sav[id]) st[id].add(v);

}

void upd(int id, int l, int r, int i, int val) {
    if (l > i || r < i) return;
    st[id].del(val);
    if (l == r) return;
    int mid = (l + r) / 2;
    upd(lps(id), l, mid, i, val);
    upd(rps(id), mid + 1, r, i, val);
}

int get(int id, int l, int r, int u, int v, int val) {
    if (l > v || r < u) return 0;
    if (u <= l && r <= v) {
        return st[id].get_xor(val);
    }
    int mid = (l + r) / 2;
    return max(get(lps(id), l, mid, u, v, val), get(rps(id), mid + 1, r, u, v, val));
}

void tintingyn() {

    cin >> Q;
    n = 1;
    rep (i, 0, Q - 1) {
        string type;
        int x, y;
        cin >> type >> x >> y;
        int t = type == "Add" ? 0 : 1;
        qs[i] = {t, x, (t == 0 ? n + 1 : y)};
        if (t == 0) G[x].push_back({y, ++n});
    }
    
    dfs(1, 0);

    // rep (i, 1, n) debug(ein[i], pf[i]);    
    build(1, 1, n);

    // return ;

    vector <int> ans(Q);
    repd (_i, Q - 1, 0) {
        auto &tv = qs[_i];
        // print(tv[0]);
        if (tv[0] == 1) {
            int u = tv[1];
            int v = tv[2];
            // debug(u, v);
            ans[_i] = get(1, 1, n, ein[v], eout[v], pf[u]);
        }
        else {
            int u = tv[1];
            int v = tv[2];
            upd(1, 1, n, ein[v], pf[v]);
        }
    }

    rep (i, 0, Q - 1) {
        auto &tv = qs[i];
        if (tv[0] == 1) cout << ans[i] << nl;
    }

}

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

    //________________________________________________________________

    #define TASK "3"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    //________________________________________________________________
    
    //  CODE FROM HERE ...! 





    int num_test = 1; 
    // cin >> num_test;

    while(num_test--) {

        tintingyn();

    }


    cerr << '\n' << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s\n" << nl;

    return 0;
}

Compilation message

klasika.cpp: In function 'void tintingyn()':
klasika.cpp:315:17: warning: unused variable 'u' [-Wunused-variable]
  315 |             int u = tv[1];
      |                 ^
klasika.cpp: In function 'int main()':
klasika.cpp:337:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  337 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:338:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  338 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	54 ms	70728 KB	Output is correct
2	Correct	69 ms	69448 KB	Output is correct
3	Correct	65 ms	73544 KB	Output is correct
4	Correct	60 ms	69716 KB	Output is correct
5	Correct	49 ms	70728 KB	Output is correct
6	Correct	56 ms	69400 KB	Output is correct
7	Correct	63 ms	69448 KB	Output is correct
8	Correct	61 ms	69848 KB	Output is correct
9	Correct	65 ms	69192 KB	Output is correct
10	Correct	56 ms	69456 KB	Output is correct
11	Correct	61 ms	69464 KB	Output is correct
12	Correct	62 ms	69704 KB	Output is correct

Subtask #2

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	54 ms	70728 KB	Output is correct
2	Correct	69 ms	69448 KB	Output is correct
3	Correct	65 ms	73544 KB	Output is correct
4	Correct	60 ms	69716 KB	Output is correct
5	Correct	49 ms	70728 KB	Output is correct
6	Correct	56 ms	69400 KB	Output is correct
7	Correct	63 ms	69448 KB	Output is correct
8	Correct	61 ms	69848 KB	Output is correct
9	Correct	65 ms	69192 KB	Output is correct
10	Correct	56 ms	69456 KB	Output is correct
11	Correct	61 ms	69464 KB	Output is correct
12	Correct	62 ms	69704 KB	Output is correct
13	Correct	66 ms	71072 KB	Output is correct
14	Correct	68 ms	73100 KB	Output is correct
15	Correct	69 ms	75092 KB	Output is correct
16	Correct	82 ms	77364 KB	Output is correct
17	Correct	64 ms	70984 KB	Output is correct
18	Correct	66 ms	72960 KB	Output is correct
19	Correct	70 ms	74808 KB	Output is correct
20	Correct	82 ms	76852 KB	Output is correct
21	Correct	72 ms	70984 KB	Output is correct
22	Correct	77 ms	73016 KB	Output is correct
23	Correct	69 ms	74836 KB	Output is correct
24	Correct	78 ms	76880 KB	Output is correct

Subtask #3

0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	713 ms	312284 KB	Output is correct
2	Runtime error	670 ms	524288 KB	Execution killed with signal 9
3	Halted	0 ms	0 KB	-

Subtask #4

0 / 44.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	54 ms	70728 KB	Output is correct
2	Correct	69 ms	69448 KB	Output is correct
3	Correct	65 ms	73544 KB	Output is correct
4	Correct	60 ms	69716 KB	Output is correct
5	Correct	49 ms	70728 KB	Output is correct
6	Correct	56 ms	69400 KB	Output is correct
7	Correct	63 ms	69448 KB	Output is correct
8	Correct	61 ms	69848 KB	Output is correct
9	Correct	65 ms	69192 KB	Output is correct
10	Correct	56 ms	69456 KB	Output is correct
11	Correct	61 ms	69464 KB	Output is correct
12	Correct	62 ms	69704 KB	Output is correct
13	Correct	66 ms	71072 KB	Output is correct
14	Correct	68 ms	73100 KB	Output is correct
15	Correct	69 ms	75092 KB	Output is correct
16	Correct	82 ms	77364 KB	Output is correct
17	Correct	64 ms	70984 KB	Output is correct
18	Correct	66 ms	72960 KB	Output is correct
19	Correct	70 ms	74808 KB	Output is correct
20	Correct	82 ms	76852 KB	Output is correct
21	Correct	72 ms	70984 KB	Output is correct
22	Correct	77 ms	73016 KB	Output is correct
23	Correct	69 ms	74836 KB	Output is correct
24	Correct	78 ms	76880 KB	Output is correct
25	Correct	713 ms	312284 KB	Output is correct
26	Runtime error	670 ms	524288 KB	Execution killed with signal 9
27	Halted	0 ms	0 KB	-