Submission #1114370

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1114370	2024-11-18T17:11:38 Z	tintingyn21	Klasika (COCI20_klasika)	C++17	33 / 110	717 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	70796 KB	Output is correct
2	Correct	55 ms	70984 KB	Output is correct
3	Correct	58 ms	69456 KB	Output is correct
4	Correct	58 ms	69716 KB	Output is correct
5	Correct	58 ms	69204 KB	Output is correct
6	Correct	64 ms	69276 KB	Output is correct
7	Correct	59 ms	69452 KB	Output is correct
8	Correct	61 ms	69828 KB	Output is correct
9	Correct	56 ms	69192 KB	Output is correct
10	Correct	62 ms	69448 KB	Output is correct
11	Correct	59 ms	69436 KB	Output is correct
12	Correct	57 ms	71400 KB	Output is correct

Subtask #2

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	54 ms	70796 KB	Output is correct
2	Correct	55 ms	70984 KB	Output is correct
3	Correct	58 ms	69456 KB	Output is correct
4	Correct	58 ms	69716 KB	Output is correct
5	Correct	58 ms	69204 KB	Output is correct
6	Correct	64 ms	69276 KB	Output is correct
7	Correct	59 ms	69452 KB	Output is correct
8	Correct	61 ms	69828 KB	Output is correct
9	Correct	56 ms	69192 KB	Output is correct
10	Correct	62 ms	69448 KB	Output is correct
11	Correct	59 ms	69436 KB	Output is correct
12	Correct	57 ms	71400 KB	Output is correct
13	Correct	64 ms	70984 KB	Output is correct
14	Correct	68 ms	74812 KB	Output is correct
15	Correct	68 ms	75092 KB	Output is correct
16	Correct	69 ms	77364 KB	Output is correct
17	Correct	63 ms	72640 KB	Output is correct
18	Correct	67 ms	74552 KB	Output is correct
19	Correct	68 ms	76376 KB	Output is correct
20	Correct	77 ms	76760 KB	Output is correct
21	Correct	59 ms	70984 KB	Output is correct
22	Correct	66 ms	73016 KB	Output is correct
23	Correct	65 ms	74840 KB	Output is correct
24	Correct	77 ms	76796 KB	Output is correct

Subtask #3

0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	652 ms	312616 KB	Output is correct
2	Runtime error	717 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	70796 KB	Output is correct
2	Correct	55 ms	70984 KB	Output is correct
3	Correct	58 ms	69456 KB	Output is correct
4	Correct	58 ms	69716 KB	Output is correct
5	Correct	58 ms	69204 KB	Output is correct
6	Correct	64 ms	69276 KB	Output is correct
7	Correct	59 ms	69452 KB	Output is correct
8	Correct	61 ms	69828 KB	Output is correct
9	Correct	56 ms	69192 KB	Output is correct
10	Correct	62 ms	69448 KB	Output is correct
11	Correct	59 ms	69436 KB	Output is correct
12	Correct	57 ms	71400 KB	Output is correct
13	Correct	64 ms	70984 KB	Output is correct
14	Correct	68 ms	74812 KB	Output is correct
15	Correct	68 ms	75092 KB	Output is correct
16	Correct	69 ms	77364 KB	Output is correct
17	Correct	63 ms	72640 KB	Output is correct
18	Correct	67 ms	74552 KB	Output is correct
19	Correct	68 ms	76376 KB	Output is correct
20	Correct	77 ms	76760 KB	Output is correct
21	Correct	59 ms	70984 KB	Output is correct
22	Correct	66 ms	73016 KB	Output is correct
23	Correct	65 ms	74840 KB	Output is correct
24	Correct	77 ms	76796 KB	Output is correct
25	Correct	652 ms	312616 KB	Output is correct
26	Runtime error	717 ms	524288 KB	Execution killed with signal 9
27	Halted	0 ms	0 KB	-