Submission #520269

#	Time	Username	Problem	Language	Result	Execution time	Memory
520269		AkiYuu	Klasika (COCI20_klasika)	C++17	110 / 110	2560 ms	476808 KiB

klasika

/*

Problems:
Author: AkiYuu

*/

#include <bits/stdc++.h>
#define task "GROUP"
#define ll long long
#define ld long double
#define pb push_back
#define ffw(i,a,b) for (ll i = a; i <= b; i++)
#define fbw(i,b,a) for (ll i = b; i >= a; i--)
#define adj(v,adj,u) for (auto v : adj[u])
#define rep(i,a) for (auto i : a)
#define reset(a) memset(a, 0, sizeof(a))
#define sz(a) a.size()
#define all(a) a.begin(),a.end()

using namespace std;

void fastio(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
//	freopen(task".inp", "r", stdin);
//	freopen(task".out", "w", stdout);
}

const int mxn = 1e6 + 5;
typedef pair<ll, ll> ii;

vector < vector < int > > op;
int q;
int tin[mxn], tout[mxn], xored[mxn], timer;
int trie[30 * 200005][2], dem;
vector  < set<int> > TinBag;
vector < int > a[mxn];

void dfs(int u){
    tin[u] = ++timer;
    adj(v,a,u) dfs(v);
    tout[u] = ++timer;
}

void add(int u, ll s){
    int node = 0;

//    cout << "ADD: ";
    fbw(i,29,0){
        int x = ( s & ( 1 << i) )> 0;
//        cout << x;
        if ( trie[node][x] == 0 ){
            trie[node][x] = ++dem;
            TinBag.pb( set<int>() );
        }
        node = trie[node][x];
        TinBag[node].insert( tin[u] );
    }
//    cout << '\n';
}

ll getmax(int u , ll s){

    int node = 0;
    fbw(i,29,0){
        int x = (s & (1 << i) ) > 0;
        bool issub = 0;
        int nxt = trie[node][x ^ 1];

        if ( trie[node][x ^ 1] ){
            auto pos = TinBag[ nxt ].lower_bound(tin[u]);
            if ( pos != TinBag[ nxt ].end() && *pos <= tout[u] ) issub = 1;
            else issub = 0;
        }

        if ( issub ) {
            s ^= ( (x ^ 1) << i);
            node = trie[ node ][ x ^ 1];
        } else {
            s ^= (x << i);
            node = trie[ node ][x];
        }
    }
    return s;
}

void solve(){
    cin >> q;
    int curnode = 1;
    ffw(i,1,q){
        string type;
        ll u , v;
        cin >> type >> u >> v;
        if ( type == "Add") {
            a[u].pb(++curnode);
            xored[curnode] = xored[u] ^ v;
            op.pb({0,curnode,xored[curnode]});
        } else {
            op.pb({1,u,v});
        }
    }
    TinBag.pb( set<int>() );
    dfs(1);
    add(1, xored[1]);
    for ( auto i : op){
        if ( i[0] == 0)
            add(i[1], i[2]);
        else
            cout << getmax(i[2], xored[ i[1] ]) << '\n';
    }
}

int main(){
	fastio();
	int t = 1;
//	cin >> t;
	while (t--)
	solve();
}

Compilation message (stderr)

klasika.cpp: In function 'void solve()':
klasika.cpp:101:22: warning: narrowing conversion of 'u' from 'long long int' to 'int' [-Wnarrowing]
  101 |             op.pb({1,u,v});
      |                      ^
klasika.cpp:101:22: warning: narrowing conversion of 'u' from 'long long int' to 'int' [-Wnarrowing]
klasika.cpp:101:24: warning: narrowing conversion of 'v' from 'long long int' to 'int' [-Wnarrowing]
  101 |             op.pb({1,u,v});
      |                        ^
klasika.cpp:101:24: warning: narrowing conversion of 'v' from 'long long int' to 'int' [-Wnarrowing]

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