Submission #1306380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306380		Jean7	Klasika (COCI20_klasika)	C++20	110 / 110	289 ms	133964 KiB

klasika

#include <bits/stdc++.h>
#define int long long

using namespace std ;

const int N = 2e5+5 ;
const int L = 31 ;
const int O = 1e18 ;

vector <pair<int,int>> g[N] , v[N] ;
int q , n , tt[N] , pre[N] , ans[N] ;

struct Trie {
    int tree[N*L][2] , time[N*L] , idx = 1 ;
    Trie () {
        for ( int i = 0 ; i < N*L ; i++ ) {
            time[i] = O ;
        }
    }
    void init () {
        for ( int i = 1 ; i <= idx ; i++ ) {
            time[i] = O ;
            memset ( tree[i] , 0 , sizeof(tree[i]) ) ;
        }
        idx = 1 ;
    }
    void update ( int x , int id ) {
        int cur = 1 ;
        for ( int i = L-1 ; i >= 0 ; i-- ) {
            bool b = ( x & (1ll<<i) ) ;
            if ( !tree[cur][b] ) {
                idx++ ;
                tree[cur][b] = idx ;
            }
            cur = tree[cur][b] ;
            time[cur] = min ( time[cur] , id ) ;
        }
    }
    int query ( int x , int id ) {
        int cur = 1 , ret = 0 ;
        for ( int i = L-1 ; i >= 0 ; i-- ) {
            bool b = ( x & (1ll<<i) ) ;
            if ( time[tree[cur][b^1]] < id ) {
                ret |= (1ll<<i) ;
                cur = tree[cur][b^1] ;
            }
            else {
                cur = tree[cur][b] ;
            }
        }
        return ret ;
    }
} tr ;

struct Sack {
    int sz[N] ;
    vector <int> sub[N] ;
    void build ( int i ) {
        sz[i] = 1 ;
        for ( auto [it,w] : g[i] ) {
            pre[it] = pre[i] ^ w ;
            build ( it ) ;
            sz[i] += sz[it] ;
        }
    }
    void dfs ( int i , bool o ) {
        int big = 0 ;
        for ( auto [it,w] : g[i] ) {
            if ( sz[it] > sz[big] ) {
                big = it ;
            }
        }
        for ( auto [it,w] : g[i] ) {
            if ( it != big ) {
                dfs ( it , 0 ) ;
            }
        }
        if ( big ) {
            dfs ( big , 1 ) ;
            swap ( sub[i] , sub[big] ) ;
        }
        sub[i].push_back(i) ;
        tr.update ( pre[i] , tt[i] ) ;
        for ( auto [it,w] : g[i] ) {
            if ( it != big ) {
                for ( auto x : sub[it] ) {
                    sub[i].push_back(x) ;
                    tr.update ( pre[x] , tt[x] ) ;
                }
            }
        }
        for ( auto [x,id] : v[i] ) {
            ans[id] = tr.query ( pre[x] , id ) ;
        }
        if ( !o ) {
            tr.init () ;
        }
    }
} stl ;

inline void solve () {
    cin >> q ;
    n++ ;
    for ( int i = 1 ; i <= q ; i++ ) {
        ans[i] = -1 ;
        string op ;
        int x , y ;
        cin >> op >> x >> y ;
        if ( op[0] == 'A' ) {
            n++ ;
            tt[n] = i ;
            g[x].push_back({n,y}) ;
        }
        else {
            v[y].push_back({x,i}) ;
        }
    }
    stl.build ( 1 ) ;
    stl.dfs ( 1 , 0 ) ;
    for ( int i = 1 ; i <= q ; i++ ) {
        if ( ans[i] != -1 ) {
            cout << ans[i] << "\n" ;
        }
    }
}

signed main () {
    //freopen ( ".in" , "r" , stdin ) ;
    //freopen ( ".out" , "w" , stdout ) ;
    ios_base::sync_with_stdio(0) ;
    cin.tie(0) ;
    cout.tie(0) ;
    int tc = 1 ;
    //cin >> tc ;
    while ( tc-- ) {
        solve() ;
    }
    return 0 ;
}

///  JJJJJJJ EEEEEEE  AAAAA  NN   NN 7777777
///     JJ   EE      AA   AA NNN  NN     77
///     JJ   EEEEEE  AAAAAAA NN N NN    77
///  JJ JJ   EE      AA   AA NN  NNN   77
///  JJJJJ   EEEEEEE AA   AA NN   NN  77

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